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