图的着色与色数问题 第一步：着色问题的基本定义 图的着色是指对图的顶点、边或面分配颜色，使得相邻元素颜色不同。最常见的顶点着色定义如下： 给定无向图 \( G = (V, E) \)，一个 正常k-顶点着色 （proper k-vertex coloring）是将颜色集合 \(\{1, 2, ..., k\}\) 分配给每个顶点，满足任意相邻顶点颜色不同。 若图 \(G\) 存在正常k-顶点着色，则称 \(G\) 是 k-可着色的 （k-colorable）。 色数 （chromatic number）\(\chi(G)\) 是使 \(G\) 是k-可着色的最小k值。例如，偶圈的色数为2，奇圈的色数为3。 第二步：着色与图结构的关系 色数与图的局部结构密切相关： 团与色数下界 ：若图包含大小为 \(r\) 的团（完全子图 \(K_ r\)），则 \(\chi(G) \geq r\)，因为团中所有顶点必须互异色。 最大度与上界 ：贪心着色算法证明 \(\chi(G) \leq \Delta(G) + 1\)，其中 \(\Delta(G)\) 为最大度。更精确的布鲁克斯定理（Brooks' theorem）指出，若图不是完全图或奇圈，则 \(\chi(G) \leq \Delta(G)\)。 奇圈与二部图 ：二部图（无奇圈）的色数为2；反之，色数为2的图必为二部图。 第三步：着色问题的计算复杂性 判定“图是否k-可着色”是NP完全问题（k≥3）。即使k=3，对平面图、最大度为4的图仍是NP困难的。 例外：二部图（k=2）可用广度优先搜索在多项式时间内判定。 近似难度 ：除非P=NP，色数问题无法在多项式时间内近似到 \(O(n^{1-\epsilon})\) 倍（对于任意 \(\epsilon>0\)）。 第四步：着色推广与变种 边着色 ：对边分配颜色，使相邻边颜色不同。维辛定理（Vizing's theorem）指出边色数 \(\chi'(G)\) 满足 \(\Delta(G) \leq \chi'(G) \leq \Delta(G)+1\)。 列表着色 （List coloring）：每个顶点v有专属颜色列表 \(L(v)\)，只能从列表中选色。列表色数 \(\chi_ l(G)\) 可能大于 \(\chi(G)\)。 全着色 （Total coloring）：同时对顶点和边着色，要求相邻顶点、相邻边、关联边与顶点均异色。 第五步：着色与图论经典定理 四色定理 ：任何平面图是4-可着色的（计算机辅助证明）。 五色定理 ：平面图是5-可着色的（可人工证明，基于欧拉公式和极小反例）。 海伍德地图定理 （Heawood map theorem）：对可定向曲面S，其上所有图的最大色数由 \(\left\lfloor \frac{7+\sqrt{1+48g}}{2} \right\rfloor\) 给出（g为亏格）。 第六步：色多项式与代数方法 色多项式 \(P(G,k)\) 表示用k种颜色对G正常着色的方案数，是k的多项式。 递推关系：\(P(G,k) = P(G-e, k) - P(G/e, k)\)（G-e为删边，G/e为缩边）。 性质：色数 \(\chi(G)\) 是使 \(P(G,k)>0\) 的最小整数k。 第七步：现代研究方向 强着色猜想 （Strong edge coloring）：要求距离≤2的边异色。 图着色与概率方法 ：利用局部引理证明稀疏图可着色。 分布式着色算法 ：在LOCAL模型下研究着色问题的局部计算复杂性。