數學分支圖論中,色臨界圖或臨界圖(英語:critical graph)是圖染色問題中一類特殊的圖,從此類圖中,移除任何一邊或一點,皆會使圖的色數減少。這一類圖具有一些非常好的性質,能在很多證明定理中發揮用處。
定義
相關定義
基本性質
- 是一個沒有孤立點的色臨界圖,當且僅當對任意 。
- 證明:" "由定義可知顯然。" ":由於 。所以 。
- 設G是一個 -色臨界圖,則對任意 ,存在一種使用 種顏色的恰當的染色方式使得 種顏色均出現在鄰域 中。
- 證明:由於色臨界圖的定義知, 。所以存在一種使用前 種顏色對 的恰當的染色方式。然後再對 進行染色,則必須有 種顏色均出現在 中,否則可以用前 種色中沒有在出現 的顏色對 染色,那麼就得到用前 顏色對 染色的方法,與 矛盾。
- 設G是一個 -色臨界圖,則對任意 ,任意使用 種顏色對 的恰當的染色方式均將 兩端點染成相同顏色。
- 證明:如果存在一種使用 種顏色對 的恰當的染色方式使得 兩端點染成不同顏色,那麼這種方式同樣能對 使用,這樣與 矛盾。
相關定理
狄拉克定理
任意一個 -色臨界圖均為 -邊連通的。[1]:211
證明用到以下引理:
凱南(Kainen)引理
設 的最小染色數 ,並且 是對 的一個劃分。如果 在 上導出子圖 均是 可染色的,那麼 中至少有 條邊。[1]:211
證明:
由於 均是 可染色的,可以把 劃分為 個獨立集 ,把 劃分為 個獨立集 。如果 之間邊少於 條,則對 進行染色。先對 中的點染上 種顏色。再分別對 逐獨立集染色,並且染每個獨立集時,與其相鄰以及染完色的獨立集個數少於 個,所以可在 中顏色中選擇餘下某種對其恰當染色。這樣就對 使用 種顏色恰當染色,與 矛盾。引理證明完畢。
回到原證明,如果 不是 -邊連通的。那麼存在 條邊 使得 不是連通圖,取其一個連通分支 ,令 。由於不連通性可知 的邊皆屬 。又 是色臨界圖,有 ,所以均是 可染色。利用凱南引理可知, 的邊數至多是 ,但 ,矛盾。
定理2:
如果 是 -色臨界圖,那麼 的割集均不是團。特別說明的是,如果 有一個割集含有兩個點 ,那麼 並且 存在一個 -葉 使得 。[1]
參考內容