图染色

每条边提出一个局部“不许同色”约束，染色要让所有约束同时成立。一个顶点选色后，会占用其所有未染邻点的一种选择；影响沿边传播，顶点处理次序因而可能让同一套贪心规则产生截然不同的结果。

把颜色类看成独立集后，问题的整体图像更清楚：我们正在把一批彼此冲突的对象分装进若干槽，每个槽内部不能含边。颜色标签只是槽名，真正的结构是顶点划分。

路径与偶圈可沿边交替使用两色。奇圈交替到最后一条边时，两端被迫同色，因此两色不够；给其中任一点第三种颜色即可完成染色。这一失败机制正是二分图奇圈判据的着色版本。

贪心染色按某个顶点顺序处理，每次选当前最小可用颜色。顶点至多看见 $d(v)$ 种邻色，因此总能用至多 $\mathrm{\Delta }(G)+1$ 种颜色；这是对算法输出的上界，不说明输出达到最优。

次序依赖可以在 crown graph 中放大。令两侧为 $u_1,\dots ,u_n$ 与 $v_1,\dots ,v_n$，保留所有跨侧边但删去 $u_i{v}_i$。该图是二分图，两色足够；若按

运行 first-fit，非相邻的一对 $u_i,v_i$ 会共同获得一种新颜色，最终使用 $n$ 色。输出随顶点次序改变，不能作为图的不变量。

自环要求 $c(v)\ne c(v)$，所以含自环图没有正常顶点染色。平行边重复同一个异色约束，不改变可行染色集合。非空无边图可用一种颜色；零阶图存在到空调色板的唯一空函数，色数是否记为零留给参数页约定。

列表染色为每个顶点分别限制可用颜色，边染色则给边赋色并让关联边异色。它们不能只用普通顶点染色的 $k$-可行性判断；即使符号和贪心图像相似，输入约束已经改变。

每个团中的顶点两两相邻，必须使用不同颜色，因此 $\omega (G)$ 给出任何着色所需颜色数的下界。贪心法给出 $\mathrm{\Delta }+1$ 上界；Brooks 定理公理库Brooks 定理Brooks' theorem除完全图和奇环外，连通图色数不超过其最大度数。进一步说明，除完全图和奇圈外，连通简单图可把上界降到 $\mathrm{\Delta }$。

二分图公理库二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。恰是可二染图，也就是没有奇圈的图。平面图公理库平面图Planar graph · Plane graph可把顶点与边嵌入平面且除公共端点外没有交叉的抽象图。的四色定理则保证四种颜色总够，但具体嵌入不是顶点着色输入的一部分；地图区域先要按共享边界关系构成对偶式邻接图。

考试排程可把考试作为顶点，把有学生同时参加的两门考试连边；同色考试即可放在同一时段。若时段还有教室总容量、教师连续授课或三门课联合冲突等聚合限制，单纯的成对冲突图不再完整，需要额外约束。

一般图的最优着色计算困难，实践中常先构造一个可行染色作为上界，再用团、松弛或分支搜索产生下界。上、下界相遇时才得到最优性证书；只展示一份看起来紧凑的染色仍不能证明颜色最少。