概念

顶点染色

用最少的颜色使相邻顶点异色即为色数；平面图四色定理断言任何地图只需四色，Brooks 定理给出非完全图色数的上界。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

顶点染色图论

01定义

顶点染色为相邻顶点分配不同颜色，所需最少颜色数即色数

\chi(G)

。四色定理断言任何平面图

\chi\leq 4

；Brooks 定理说明连通图色数不超过最大度（完全图与奇圈除外）——染色是图论极值问题的明星。

3-染色：相邻异色，χ(G) = 所需最少颜色数

Brooks 定理： $\chi\leq\Delta$ （完全图、奇圈取等）；贪心算法给出 $\chi\leq\Delta+1$ ；四色定理把平面图整体压到 4。

1976 年阿佩尔与哈肯以 1200 小时计算机验证 1936 种构型完成证明——第一个倚重计算机的主流数学定理，引发「证明是什么」的哲学讨论。

色多项式 $P(G,k)$ 计数 $k$ -染色方案（ $P(K_n,k)=k(k-1)\cdots$ ）；列表染色、边染色、流问题层层推广，与统计物理配分函数同源。

\chi(G)\leq\Delta(G)+1,\quad\chi(\text{平面图})\leq 4

格斯里 1852 年提出四色猜想；肯普 1879 年的「证明」十一年后被赫伍德推翻并引出五色定理；1976 年计算机辅助证明最终成立。

考试排考（科目=顶点、同考生科目相连）、寄存器分配（编译器核心）、频率分配与地图着色——冲突回避问题的统一模型。

贪心着色：最少用色数 ≤ Δ+1逐步着色：相邻节点不得同色

step 已着色节点数0