布鲁克定理
布鲁克定理(英語:)[1]是图论中图着色问题的一个重要定理,它描述了图的色数和最大度之间的关系。根据布鲁克定理,在一个连通图G中,如果G不是完全图或奇环,设G的顶点的最大度为Δ(G),则G可以被Δ-着色,即G可以被染成Δ种颜色,使得相邻点颜色互不相同。
进一步阐释
图着色问题有一个贪心算法(greedy coloring)[2],将颜色标号为,将图G的顶点排序为,按顺序对顶点进行染色,选择与已染色的邻点不同的标号最小的颜色,作为的着色。
经观察,此算法最多使用Δ(G)+1种颜色。这个算法并不能保证得到最小的着色数,但是它给出了图G色数的一个上界,即。
根据布鲁克定理,不等式取等当且仅当G为完全图或奇环。
定理的证明思路
当G为完全图时,,,当G为奇环时,,,均满足。
下面我们证明,当G不是完全图或奇环时,。设k=Δ(G),不妨k≥3,否则转化成容易验证的简单情况。我们希望把G的顶点排成合适的顺序,使得每个点至多有k-1个邻点在它前面染色,这样我们就可以达成最多使用k种颜色的目标。
情况1:G不是k-正则图。
我们选择G中度小于k的点v最后染色。从v出发对图G进行深度优先遍历,按照DFS序的逆序排列G的节点。这样,除v之外每个节点都有一个邻点排在它的后面,故只有小于等于k-1个邻点排在它前面,而,故也只有小于等于k-1个邻点排在它前面,满足k-着色的条件。
情况2:G是k-正则图,且G有一个割点v。
设C为G-v的一个连通分量,则v在C中的度,我们使用贪婪算法对着色,使得v为最后一个被染色的点,可以得到的k-着色。使用这种方法对G-v的每一个连通分量和v的并进行着色,使得v在这些着色中使用同一种颜色(但都小于等于第k种颜色),我们得到G的一个k-着色。
情况3:G是k-正则图,且G无割点。
我们希望找到一个顶点,使得它有两个邻点,满足不相邻,且连通。如果这样的存在,我们把排在最前面,仍按照从出发的DFS序逆序排列其余点。这样我们能得到一个k-着色,因为除之外的点只有小于等于k-1个邻点排在它前面,而的邻点颜色相同,故仅需使用前k种颜色。
现在我们说明可以找到这样的。任取G的一个顶点x,如果点连通度(最小割点集的阶数),则令,令为和距离为2的顶点,为的共同邻点即可(这样的是存在的,因为G是非完全图的正则图)。
如果,则令。因为G无割点,所以x与G-x的每一个叶区块(leaf block)都相邻。取x的在两个不同叶区块中的邻点,则不相邻,且不是G-x的割点,因此连通。因为k≥3,所以连通。即证。
參考資料
- Brooks, R. L., , Mathematical Proceedings of the Cambridge Philosophical Society, 1941, 37 (2): 194–197, doi:10.1017/S030500410002168X
- Mitchem, John, , The Computer Journal, 1976, 19 (2): 182–183, MR 0437376, doi:10.1093/comjnl/19.2.182
- Lovász, L., , Journal of Combinatorial Theory, Series B, 1975, 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1