色数

一份合法染色回答“这些颜色够不够”，色数回答“最少要多少”。前者给上界，后者还要求排除所有更小调色板。最优性证明通常要把一份构造和一项不可行性理由配在一起。

色数衡量冲突能否压缩成少量独立组，无法由边数或最大团单独决定。局部看不到三角形，只说明团下界至多为二；许多较长的相互作用仍可共同迫使更多颜色。

完全图 $K_n$ 的每对顶点都相邻，故 $\chi (K_n)=n$。偶圈可以交替二染，奇圈两色必在闭合处冲突且三色可行，因此

在五圈 $C_5$ 上加入一个与圈上所有顶点相邻的中心，得到轮图 $W_6$。外圈需要三色，中心又与三种外圈颜色都冲突，所以 $\chi (W_6)=4$；最大团却只有“中心加一条圈边”形成的三角形，故 $\omega (W_6)=3$。团下界在这个小结构上已经不紧。

差距可以任意大。Mycielski 构造从 $C_5$ 出发反复产生无三角图，同时让色数每次增加一；于是存在 $\omega (G)=2$ 而 $\chi (G)$ 任意大的图。高色数不必由一个巨大完全子图局部见证。

贪心算法可能使用远多于 $\chi (G)$ 的颜色，因为输出依赖顶点顺序。它仍然提供可靠上界：若某次运行用了 $q$ 色，就证明 $\chi (G)\le q$。只有再获得同样大小的下界，才能宣称求出了色数。

色数针对正常顶点染色。边色数、列表色数、分数色数和圆染色数优化不同的可行对象；一个参数上的等式或界不能凭“都叫染色”转移到另一个参数。

图是二分图理路二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。当且仅当 $\chi (G)\le 2$。若图含边，等号为二；若非空而没有边，色数降为一；零阶图的色数按本页约定为零。这一边界把奇圈检测、二分划分和两色可行性连成同一个判据。

Brooks 定理理路Brooks 定理Brooks' theorem除完全图和奇环外，连通图色数不超过其最大度数。说明，连通简单图若既非完全图也非奇圈，则 $\chi (G)\le \mathrm{\Delta }(G)$。它识别了贪心通用界 $\mathrm{\Delta }+1$ 的精确结构例外；其余图可能远少于 $\mathrm{\Delta }$ 色，定理只承诺上界。

对平面图理路平面图Planar graph可把顶点与边嵌入平面且除公共端点外没有交叉的抽象图。，四色定理给出 $\chi (G)\le 4$；平面二分图甚至只需两色。完美图理路完美图Perfect graph每个顶点诱导子图的色数都等于最大团大小；区间图可用资源分配与同时重叠证书证明这一性质。要求每个诱导子图都满足 $\chi =\omega$；区间图的资源分配算法能同时给出最优染色和同样大小的重叠团，从而把这个要求变成可核验的证书。

冲突调度中，$\chi (G)$ 是忽略容量与时长后所需时槽的理论下限。若实际方案使用更多时槽，原因可能来自求解未最优，也可能来自模型外约束；先区分这两种来源，才能正确解释色数与排程结果的差异。