布鲁克斯定理

图论中，布鲁克定理（英语：Brooks' theorem）^[1] 描述了图的着色数与图中最大度数的关系，提供了图着色数的一个上界。定理断言，若连通图G中，每个顶点都不多于Δ个邻居，且G不是完全图或奇环，则G可以被Δ-着色，即G可以被染成Δ种颜色，使得相邻点颜色互不相同。

背景

图染色数

主条目：图着色问题

考虑为${\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=只需其一 (帮助)