布鲁克斯定理

图染色数

考虑为${\displaystyle G}$ 的顶点染色，而使每边的两端不同色。以符号表示，条件是：对于图${\displaystyle G}$ 中任意两个顶点${\displaystyle u,v}$ ，如果${\displaystyle uv\in E(G)}$ ，那么${\displaystyle u,v}$ 所染成的颜色不同。

对于图${\displaystyle G}$ ，如果存在一个${\displaystyle k}$ 种颜色的恰当染色方案，称${\displaystyle G}$ 可染${\displaystyle k}$ 色（或“${\displaystyle k}$ 可着色”）。在所有满足条件的${\displaystyle k\in \mathbb {Z_{+}} }$ 中，称最小的那个${\displaystyle k}$ 称为染色数${\displaystyle \chi (G)}$ 。

图最小染色数和图最大度数关系

图${\displaystyle G}$ 的最大度记作${\displaystyle \Delta (G)}$ 。对于任意图${\displaystyle G}$ ，${\displaystyle \chi (G)\leq \Delta (G)+1}$ 始终成立。但是这个上界并不足够紧。而布鲁克斯定理提供了一个更紧的上界。

图着色问题有一个贪心染色法（greedy coloring）^[2]，将颜色标号为${\displaystyle 1,2,...,\Delta (G)+1}$ ，将图G的顶点排序为${\displaystyle v_{1},v_{2},...,v_{n}}$ ，按顺序对顶点${\displaystyle v_{i}}$ 进行染色。染${\displaystyle v_{i}}$ 时，其邻居至多有${\displaystyle \Delta (G)}$ 个，所以已染色的邻居中，至多衹用了${\displaystyle \Delta (G)}$ 种色，尚有某种色未用，可选择该种色作为${\displaystyle v_{i}}$ 的着色。

根据布鲁克斯定理，不等式${\displaystyle \chi (G)\leq \Delta (G)+1}$ 取等当且仅当G为完全图或奇环。当G为完全图时，${\displaystyle \chi (G)=n}$ ，${\displaystyle \Delta (G)=n-1}$ ，当G为奇环时，${\displaystyle \chi (G)=3}$ ，${\displaystyle \Delta (G)=2}$ ，均满足${\displaystyle \chi (G)=\Delta (G)+1}$ 。

如果${\displaystyle G}$ 是一个连通图，而且${\displaystyle G}$ 不是奇环${\displaystyle C_{2n+1}}$ 或者完全图${\displaystyle K_{n}}$ ，那么${\displaystyle \chi (G)\leq \Delta (G)}$ 。其中${\displaystyle \chi (G)}$ 是图${\displaystyle G}$ 的最小着色数，${\displaystyle \Delta (G)}$ 是图${\displaystyle G}$ 中点的最大度数。

此处给出洛瓦兹·拉兹洛^[3]的一个证明（亦见诸^[4]）。

记${\displaystyle k=\Delta (G)}$ 。当${\displaystyle k=0,1}$ 的时候，${\displaystyle G}$ 是完全图。当${\displaystyle k=2}$ 的时候，由于${\displaystyle G}$ 不是奇环，那么${\displaystyle G}$ 要么是一条路径${\displaystyle P}$ ，或者偶环${\displaystyle C_{2n}}$ 。此时${\displaystyle \chi (G)=2=\Delta (G)}$ 。所以，衹需从${\displaystyle k\geq 3}$ 开始考虑。分下列三种情况：

G不是k正则图

选择G中度小于k的点${\displaystyle v_{0}}$ 最后染色。由于${\displaystyle G}$ 连通，有某种排序方式使得除${\displaystyle v_{0}}$ 之外，每个节点都有一个邻点排在它的后面：例如从${\displaystyle v_{0}}$ 出发对图G进行深度优先遍历，按照DFS序的逆序排列G的节点。故只有小于等于k - 1个邻点排在它前面，这样，只有小于等于k - 1个邻点排在它前面，而${\displaystyle d(v_{0})\leq k-1}$ ，故也只有小于等于k - 1个邻点排在它前面，按该次序的贪心染色最多衹用k种色。

若要避免术语“DFS”，可以构造下列集合${\displaystyle \{S_{i}\}}$ 直到里面包含${\displaystyle G}$ 中所有顶点：

${\displaystyle {\begin{aligned}S_{0}&={v_{0}}\\S_{1}&=N(v_{0})\\S_{2}&=N(S_{1})-S_{1}-S_{0}\\\dots \\S_{l}&=N(S_{l-1})-S_{l-1}-S_{l-2}\dots -S_{0}\end{aligned}}}$ 

然后可以用上述贪心染色算法对图${\displaystyle G}$ 进行染色。染色顺序为：先染${\displaystyle S_{l}}$ 中的点，再染${\displaystyle S_{l-1}}$ 中的点，一直这么下去直到染完${\displaystyle S_{0}}$ 中的点。这种算法使用${\displaystyle l}$ 种颜色就能完成。当染到点${\displaystyle u\in S_{i}(i\neq 0)}$ 时，${\displaystyle u}$ 在${\displaystyle S_{i-1}}$ 中至少有一个邻居，所以${\displaystyle u}$ 邻居中至多只有${\displaystyle k-1}$ 个被染色过，所以能对${\displaystyle u}$ 进行染色。

当染点${\displaystyle v_{0}}$ 的时候，由于${\displaystyle d(v_{0})<k}$ ，${\displaystyle v_{0}}$ 邻居中至多只有${\displaystyle k-1}$ 个被染色过，所以同样能对${\displaystyle v_{0}}$ 进行染色。所以用${\displaystyle k}$ 种颜色对${\displaystyle G}$ 恰当染色。

G是k正则图但有割点

假设割点为${\displaystyle u}$ ，那么${\displaystyle G'=G-\{u\}}$ 就不是连通图，设${\displaystyle G'}$ 有${\displaystyle t}$ 个连通分量${\displaystyle G_{1},G_{2},\dots ,G_{t}}$ 。对于任意一个连通分支${\displaystyle G_{i}}$ ，考虑${\displaystyle H_{i}=G_{i}\cup \{u\}}$ 。由于${\displaystyle u}$ 在${\displaystyle H_{i}}$ 的度数小于${\displaystyle k}$ ，${\displaystyle \Delta (H_{i})<k}$ 。由前述贪心染色算法可知，${\displaystyle H_{i}}$ 可染${\displaystyle k}$ 色。然后只需令这些染色方案中${\displaystyle u}$ 所染的颜色一样（如果不一样，将所有点染的颜色重新排列一下），就能拼成${\displaystyle G}$ 的染色方案，所以可用${\displaystyle k}$ 种颜色对${\displaystyle G}$ 恰当染色。

G是k正则图且无割点

由于${\displaystyle G}$ 中没有割点，${\displaystyle G}$ 是2连通图（英语：Biconnected graph）。断言可以找到一个顶点${\displaystyle u}$ ，使得它有两个邻点${\displaystyle v_{1},v_{2}}$ ，满足${\displaystyle v_{1},v_{2}}$ 不相邻，且${\displaystyle G-\{v_{1},v_{2}\}}$ 连通。如果这样的${\displaystyle u,v_{1},v_{2}}$ 存在，就可以先将${\displaystyle v_{1},v_{2}}$ 染成同色，然后贪心地为其他点染色，使${\displaystyle u}$ 最后染。这样贪心染法衹用不超过${\displaystyle k}$ 种色，因为除${\displaystyle u}$ 之外的点，只有小于等于${\displaystyle k-1}$ 个邻点排在它前面，而${\displaystyle u}$ 又有两个邻点${\displaystyle v_{1},v_{2}}$ 同色，故${\displaystyle u}$ 的邻域衹用前${\displaystyle k-1}$ 种色，尚有余下颜色可用。以下说明为何有此种${\displaystyle u,v_{1},v_{2}}$ 。

如果${\displaystyle G}$ 是3连通的，则可以选取距离为2的两点${\displaystyle v_{1},v_{2}}$ （因为${\displaystyle G}$ 不是完全图），及其公共邻点${\displaystyle u}$ 。如此有${\displaystyle v_{1}v_{2}\notin E(G)}$ ，又由于${\displaystyle G}$ 是3连通的，${\displaystyle G-\{v_{1},v_{2}\}}$ 是连通图，即为所求。

仅剩${\displaystyle G}$ 是2连通但不是3连通的情况。此时有顶点${\displaystyle u}$ 使${\displaystyle G-u}$ 仅为1连通，考虑${\displaystyle G-u}$ 各个双连通分支（英语：biconnected component），之间以割点连接，组成一棵树。因为${\displaystyle G-u}$ 不是2连通，该树至少有两个叶区块（leaf block），设为${\displaystyle B_{1},B_{2}}$ 。又因为${\displaystyle G}$ 无割点，所以${\displaystyle G-u}$ 的每一个叶区块中，必有某个非割点与${\displaystyle u}$ 相邻。于是，可以在${\displaystyle B_{1},B_{2}}$ 中各取${\displaystyle u}$ 的邻点${\displaystyle v_{1},v_{2}}$ ，使${\displaystyle v_{1},v_{2}}$ 不是${\displaystyle G-u}$ 的割点。如此，${\displaystyle v_{1},v_{2}}$ 不相邻（否则${\displaystyle B_{1},B_{2}}$ 属同一双连通分支），且${\displaystyle G-\{u,v_{1},v_{2}\}}$ 连通。因为${\displaystyle k\geq 3}$ ，所以${\displaystyle G-\{v_{1},v_{2}\}}$ 连通。证毕。

1. ^ Brooks, R. L., On colouring the nodes of a network, Mathematical Proceedings of the Cambridge Philosophical Society（英语：Mathematical Proceedings of the Cambridge Philosophical Society）, 1941, 37 (2): 194–197, doi:10.1017/S030500410002168X 
2. ^ Mitchem, John, On various algorithms for estimating the chromatic number of a graph, The Computer Journal（英语：The Computer Journal）, 1976, 19 (2): 182–183, MR 0437376, doi:10.1093/comjnl/19.2.182 
3. ^ Lovász, L., Three short proofs in graph theory, Journal of Combinatorial Theory（英语：Journal of Combinatorial Theory）, Series B, 1975, 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1 
4. ^ Douglas B.West. Introduction to Graph Theory. Pearson Enducation. 2002. ISBN 81-7808-830-4. 

• Rigo, Michel. Advanced graph theory and combinatorics. London, UK. 2008: 90–92. ISBN 978-0-387-79711-3.  |author1=和|last1=只需其一 (帮助)
• Bondy, J. A. Graph theory. New York: Springer. 2008: 359-363. ISBN 978-1-84628-969-9.  |author1=和|last1=只需其一 (帮助)