布魯克斯定理

圖的色數與最大度之關係

圖論中,布魯克定理(英語:Brooks' theorem[1] 描述了圖的着色數與圖中最大度數的關係,提供了圖着色數的一個上界。定理斷言,若連通圖G中,每個頂點都不多於Δ個鄰居,且G不是完全圖奇環,則G可以被Δ-着色,即G可以被染成Δ種顏色,使得相鄰點顏色互不相同。

背景

圖染色數

考慮為 的頂點染色,而使每邊的兩端不同色。以符號表示,條件是:對於圖 中任意兩個頂點 ,如果 ,那麼 所染成的顏色不同。

對於圖 ,如果存在一個 種顏色的恰當染色方案,稱 可染 色(或「 可着色」)。在所有滿足條件的 中,稱最小的那個 稱為染色數 

圖最小染色數和圖最大度數關係

 的最大記作 。對於任意圖  始終成立。但是這個上界並不足夠緊。而布魯克斯定理提供了一個更緊的上界。

圖着色問題有一個貪心染色法greedy coloring[2],將顏色標號為 ,將圖G的頂點排序為 ,按順序對頂點 進行染色。染 時,其鄰居至多有 個,所以已染色的鄰居中,至多衹用了 種色,尚有某種色未用,可選擇該種色作為 的着色。

根據布魯克斯定理,不等式 取等當且僅當G為完全圖或奇環。當G為完全圖時,  ,當G為奇環時,  ,均滿足 

定理敍述

如果 是一個連通圖,而且 不是奇環 或者完全圖 ,那麼 。其中 是圖 的最小着色數, 是圖 中點的最大度數。

定理證明

此處給出洛瓦茲·拉茲洛[3]的一個證明(亦見諸[4])。

 。當 的時候, 是完全圖。當 的時候,由於 不是奇環,那麼 要麼是一條路徑 ,或者偶環 。此時 。所以,衹需從 開始考慮。分下列三種情況:

G不是k正則圖

選擇G中度小於k的點 最後染色。由於 連通,有某種排序方式使得除 之外,每個節點都有一個鄰點排在它的後面:例如從 出發對圖G進行深度優先遍歷,按照DFS序的逆序排列G的節點。故只有小於等於k - 1個鄰點排在它前面,這樣,只有小於等於k - 1個鄰點排在它前面,而 ,故也只有小於等於k - 1個鄰點排在它前面,按該次序的貪心染色最多衹用k種色。

若要避免術語「DFS」,可以構造下列集合 直到裡面包含 中所有頂點:

 

然後可以用上述貪心染色算法對圖 進行染色。染色順序為:先染 中的點,再染 中的點,一直這麼下去直到染完 中的點。這種算法使用 種顏色就能完成。當染到點 時,  中至少有一個鄰居,所以 鄰居中至多只有 個被染色過,所以能對 進行染色。

當染點 的時候,由於  鄰居中至多只有 個被染色過,所以同樣能對 進行染色。所以用 種顏色對 恰當染色。

Gk正則圖但有割點

假設割點 ,那麼 就不是連通圖,設  連通分量 。對於任意一個連通分支 ,考慮 。由於  的度數小於  。由前述貪心染色算法可知, 可染 色。然後只需令這些染色方案中 所染的顏色一樣(如果不一樣,將所有點染的顏色重新排列一下),就能拼成 的染色方案,所以可用 種顏色對 恰當染色。

Gk正則圖且無割點

由於 中沒有割點, 2連通圖英語Biconnected graph。斷言可以找到一個頂點 ,使得它有兩個鄰點 ,滿足 不相鄰,且 連通。如果這樣的 存在,就可以先將 染成同色,然後貪心地為其他點染色,使 最後染。這樣貪心染法衹用不超過 種色,因為除 之外的點,只有小於等於 個鄰點排在它前面,而 又有兩個鄰點 同色,故 的鄰域衹用前 種色,尚有餘下顏色可用。以下說明為何有此種 

如果 是3連通的,則可以選取距離為2的兩點 (因為 不是完全圖),及其公共鄰點 。如此有 ,又由於 是3連通的, 是連通圖,即為所求。

僅剩 是2連通但不是3連通的情況。此時有頂點 使 僅為1連通,考慮 各個雙連通分支英語biconnected component,之間以割點連接,組成一棵樹。因為 不是2連通,該樹至少有兩個葉區塊(leaf block),設為 。又因為 無割點,所以 的每一個葉區塊中,必有某個非割點與 相鄰。於是,可以在 中各取 的鄰點 ,使 不是 的割點。如此, 不相鄰(否則 屬同一雙連通分支),且 連通。因為 ,所以 連通。證畢。

參考文獻

  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.