图论中，布鲁克定理（） 描述了图的着色数与图中最大度数的关系，提供了图着色数的一个上界。定理斷言，若连通图G中，每個頂點都不多於Δ個鄰居，且G不是完全图或奇环，则G可以被Δ-着色，即G可以被染成Δ种颜色，使得相邻点颜色互不相同。
背景
图染色数
考慮為G的頂點染色，而使每邊的兩端不同色。以符號表示，條件是：对于图G中任意两个顶点u,v，如果uv\in E(G)，那么u,v所染成的颜色不同。
对于图G，如果存在一个k种颜色的恰当染色方案，称G可染k色（或「k可着色」）。在所有满足条件的k\in \mathbb{Z_+}中，称最小的那个k稱為染色數\chi(G)。
图最小染色数和图最大度数关系
圖G的最大度記作\Delta (G)。对于任意图G，\chi(G)\le \Delta(G)+1始终成立。但是这个上界并不足够紧。而布鲁克斯定理提供了一个更紧的上界。
图着色问题有一个贪心染色法（），将颜色标号为1,2,..., \Delta(G) +1，将图G的顶点排序为v_{1},v_{2},...,v_{n}，按顺序对顶点v_{i}进行染色。染v_i時，其邻居至多有\Delta(G)個，所以已染色的鄰居中，至多衹用了\Delta(G)種色，尚有某種色未用，可选择該種色作为v_{i}的着色。
根据布鲁克斯定理，不等式\chi(G)\leq \Delta(G)+1取等当且仅当G为完全图或奇环。当G为完全图时，\chi(G)=n，\Delta(G)=n-1，当G为奇环时，\chi(G)=3，\Delta(G)=2，均满足\chi(G)=\Delta(G)+1。
定理敍述
如果G是一个连通图，而且G不是奇环C_{2n+1}或者完全图K_n，那么\chi(G)\le \Delta(G)。其中\chi(G)是图G的最小着色数，\Delta(G)是图G中点的最大度数。
定理证明
此處给出洛瓦兹·拉兹洛的一个证明（亦見諸）。
记k=\Delta(G)。当k=0,1的时候，G是完全图。当k=2的时候，由于G不是奇环，那么G要么是一条路径P，或者偶环C_{2n}。此时\chi(G)=2=\Delta(G)。所以，衹需从k\ge3开始考虑。分下列三種情況：
G不是k正则图
选择G中度小于k的点v_0最后染色。由於G連通，有某種排序方式使得除v_0之外，每个节点都有一个邻点排在它的后面：例如从v_0出发对图G进行深度优先遍历，按照DFS序的逆序排列G的节点。故只有小于等于k - 1个邻点排在它前面，这样，只有小于等于k - 1个邻点排在它前面，而d(v_0)\leq k-1，故也只有小于等于k - 1个邻点排在它前面，按該次序的貪心染色最多衹用k種色。
若要避免術語「DFS」，可以构造下列集合\{S_i\}直到里面包含G中所有顶点：
:\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}
然后可以用上述贪心染色算法对图G进行染色。染色顺序为：先染S_l中的点，再染S_{l-1}中的点，一直这么下去直到染完S_0中的点。这种算法使用l种颜色就能完成。当染到点u\in S_i(i\neq 0)時，u在S_{i-1}中至少有一个邻居，所以u邻居中至多只有k-1个被染色过，所以能对u进行染色。
当染点v_0的时候，由于d(v_0)，v_0邻居中至多只有k-1个被染色过，所以同样能对v_0进行染色。所以用k种颜色对G恰当染色。
G是k正则图但有割点
假设割点为u，那么G'=G-\{u\}就不是连通图，设G'有t个連通分量G_1,G_2, \dots, G_t。对于任意一个连通分支G_i，考虑H_i=G_i\cup\{u\}。由于u在H_i的度數小於k，\Delta(H_i)。由前述贪心染色算法可知，H_i可染k色。然后只需令这些染色方案中u所染的颜色一样（如果不一样，将所有点染的颜色重新排列一下），就能拼成G的染色方案，所以可用k种颜色对G恰当染色。
G是k正则图且無割点
由于G中没有割点，G是2连通图。斷言可以找到一个顶点u ，使得它有两个邻点v_{1},v_{2}，满足v_{1},v_{2}不相邻，且G-\{v_{1},v_{2}\}连通。如果这样的u,v_{1},v_{2}存在，就可以先將v_{1},v_{2}染成同色，然後貪心地為其他點染色，使u最後染。这样貪心染法衹用不超過k種色，因为除u之外的点，只有小于等于k-1个邻点排在它前面，而u又有兩個邻点v_{1},v_{2}同色，故u的鄰域衹用前k-1種色，尚有餘下顏色可用。以下說明為何有此種u,v_{1},v_{2}。
如果G是3连通的，則可以選取距離為2的兩點v_1, v_2（因為G不是完全圖），及其公共鄰點u。如此有v_1 v_2\notin E(G)，又由于G是3连通的，G-\{v_1,v_2\}是连通图，即為所求。
僅剩G是2连通但不是3连通的情況。此時有頂點u使G - u僅為1連通，考慮G - u各個，之間以割點連接，組成一棵樹。因為G-u不是2連通，該樹至少有兩個叶区块（），設為B_1, B_2。又因为G无割点，所以G-u的每一个叶区块中，必有某個非割點與u相邻。於是，可以在B_1, B_2中各取u的鄰點v_1, v_2，使v_{1},v_{2}不是G-u的割点。如此，v_{1},v_{2}不相邻（否則B_1, B_2屬同一雙連通分支），且G-\{u,v_{1},v_{2}\}连通。因为k \ge 3，所以G-\{v_{1},v_{2}\}连通。證畢。
参考文献
*
*
评论 (0)