Finite Playground

To verify is human; to prove, divine.

Graph coloring theorems revisited I – Brook’s Theorem and Rubin’s Block Theorem

Leave a comment

這學期在修學校著名的組合數學課程, 課本當然是使用 Douglas B. West 的新書草稿.  其中有許多內容是全新的, 我想這會成為新一代的組合學以及圖論教科書吧?

今天要談的是圖著色中著名的定理之一 — Brooks’ Theorem, 說明只要不是完全圖或奇圈 (odd cycle), 我們便可以稍稍改進單純的上界 \Delta(G) +1\Delta.  但當初學到的證明簡直是魔術, 看不出什麼東西.  在 West 的新書中使用了 [Entringer85] 的結果, 說明為何這兩種圖比較特別.

Rubin’s Block Theorem.  令 G 為一雙連通圖; 若 G 不是完全圖或奇圈, 則 G 中有一個含有最多一條弦 (chord) 的偶圈.

很奇怪的圖結構定理, 但我們來看看要怎麼使用它!  定義圖 G 為 degree-choosable 如果對於任意的色組函數將每個圖中的點對應到一組可選擇的顏色, 且每個點上的顏色至少跟點的 degree 相同, 我們都保證可以從每組顏色中選取一種將圖適當的著色.  底下這兩個 Lemma 不難證:

Lemma 1.  給定連通圖 G 與一色組函數 L, (i) 若有某個點 v 的顏色選擇多於 degree, 則圖 G 可順利著色; (ii) 若圖 G 為雙連通, 且有兩個點上的顏色組不同, 則圖 G 可順利著色.

Lemma 2.  連通圖 G 若存在一 degree-choosable 生成子圖 H, 則圖 G 也是 degree-choosable.
Proof.  By Lemma 1(a).

利用 Lemma 1,2 與 Rubin’s Block Theorem 我們可以證明底下的若且唯若條件, 不過我們只需要唯若方向就是; 所以暫時先證一邊!

Theorem.  圖 G 不為 degree-choosable 若且唯若每個雙連通集 (block) 皆為完全圖或奇圈.
Proof.  由 Lemma 2 與 Block Theorem 我們只需要證明含有最多一條弦的偶圈是 degree-choosable; 但利用 Lemma 1(b) 這很明顯.

Brooks’ Theorem (extended).  若圖 G 不是完全圖或奇圈, 則 \chi_{\ell}(G) \le \Delta(G).
Proof.  利用上面的 Theorem 我們只需要處理當所有雙連通集都是完全圖或奇圈的情形.  如果有個點的 degree 比 \Delta(G) 小, 利用 Lemma 1(a) 就結束了; 所以 G 一定是 \Delta(G)-正則 (regular); 但在這種情況下表示我們只有一個 block (不然斷點的 degree 會有問題), 證明完成.

不過, 這其實不是我最喜歡的證明; degree-choosable 的部分可以被另一個定理取代, 並且能更增強證明的結果; 我們留到下次再介紹 Alon-Tarsi Theorem.

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s