图着色通常指顶点着色：给每个顶点分配一种颜色，使相邻顶点颜色不同。满足这一条件所需的最少颜色数叫作色数，记作 。
如果你想快速理解，可以把颜色看成不会冲突的标签。两个顶点只有在它们之间没有边时，才可以使用同一种颜色。
一分钟理解图着色的定义
在一个合法着色中，每条边连接的两个顶点颜色都不同。这就是全部规则。
所以如果 ，就同时说明两件事：
- 存在一种使用 种颜色的合法着色
- 不存在只用 种颜色的合法着色
这就是为什么色数表示的是最小值，而不只是你在某一幅图里碰巧用了多少种颜色。
除非特别说明，入门课程里说的图着色，通常都是给简单无向图的顶点着色。边着色是另一个问题，规则也不同。
色数真正衡量的是什么
颜色的名字并不重要。你可以用红、蓝、绿，也可以用标签 、、。
真正重要的是分组方式。所有同色顶点构成的集合内部都没有边，所以这个组内不存在冲突。
正是这种视角，让图着色在排课和资源分配问题中很有用。一种颜色往往表示“这些项目可以共享同一个时段”。
例题：为什么 5-环需要 3 种颜色
考虑环图 ，它的边为 和 。
先尝试用 种颜色。给 染颜色 ，给 染颜色 。那么沿着这个环，后面的着色就被迫确定为：
现在看 。它同时与 和 相邻，所以它不能因为 而用颜色 ，也不能因为 而用颜色 。
所以用 种颜色行不通。
但用 种颜色是可以的。一种合法着色是
因此
这个例子值得记住，因为它展示了一个重要规律：对于环图，偶环可以用 种颜色着色，而奇环需要 种颜色。
如何对小图进行图着色分析
有两个快速检查方法。
第一，寻找是否存在被迫产生的冲突。在上面的例子中，沿奇环交替使用两种颜色时，最后一个顶点会与两种可选颜色都发生冲突。
第二，寻找下界。如果一个图包含三角形，那么这三个顶点两两相邻，因此它们已经需要 种不同颜色。这不一定总能给出精确答案，但它能证明色数至少是 。
图着色题中的常见错误
一个常见错误是因为顶点画得很近，就把它们当成相邻。只有真正存在边，才会带来着色限制。
另一个错误是认为每个顶点都需要自己的颜色。不相邻的顶点可以重复使用同一种颜色，而高效的着色通常会尽量复用颜色。
学生有时还会把顶点着色和边着色混淆。在本页中，规则针对的是相邻顶点，不是相邻边。
最后一个错误是报告你实际用了多少种颜色，而不是所需的最少颜色数。在一个图上用了 种颜色，并不能证明它的色数就是 。
图着色有哪些应用
一个标准应用是排程。假设每个顶点表示一场考试，一条边表示两场考试有共同学生，因此不能安排在同一时间。那么一种颜色就可以表示一个时间段。
在这个模型中，色数告诉你最少需要多少个时间段。如果 ，那么只用 个时间段的合法安排就不存在。
同样的思想也出现在地图着色中，相邻区域必须颜色不同；还出现在编译器设计中，同时需要使用的变量不能共享同一个寄存器。
试试一道类似的图着色题
画一个图，顶点为 ，边为 和 。
先找出一个三角形来得到下界。然后尝试用尽可能少的颜色给这个图着色，并检查是否有相邻顶点颜色相同。如果你想继续挑战，可以在更大的图上自己设计一个版本，看看你能否证明自己的着色不仅合法，而且确实是最少的。