图着色

图着色通常指给无向图的顶点分配颜色，使每条边的两个端点颜色不同。能用 $k$ 种颜色完成，称图可 $k$ 着色；所需最少颜色数为色数 $χ (G)$ 。颜色只是类别标签，不要求真的使用红、蓝等物理颜料。

三角形与四边形

三角形的三个顶点两两相邻，必须用三种不同颜色，故 $χ (K_{3}) = 3$ 。四边形环 $C_{4}$ 可沿周长交替使用两色，故 $χ (C_{4}) = 2$ 。一个图中若出现三角形，就至少需要三色；但没有三角形不保证两色，因为五边形环虽无三角形，绕一圈交替两色后末边仍会接上相同颜色。

连通图可二着色，当且仅当它没有奇数长度的环。一方向很直观：沿任意环颜色必须交替，绕奇数步回起点会要求起点同时取两色，矛盾。反方向可从任一顶点出发，按到起点的最短路径长度奇偶给顶点分色；若存在同色相邻顶点，两条到起点的路径连同该边可导出奇环。这也刻画了二分图。

着色可表示排课冲突：把课程作顶点，同一学生不能同时参加的两门课之间连边，不同颜色代表不同时间段。模型只描述已列出的冲突；若还有限制教室容量，单纯图着色不会自动处理，需增加约束。