跳至內容

色臨界圖

維基百科,自由的百科全書

數學分支圖論中,色臨界圖臨界圖(英語:critical graph)是圖染色問題中一類特殊的,從此類圖中,移除任何一邊或一點,皆會使圖的色數減少。這一類圖具有一些非常好的性質,能在很多證明定理中發揮用處。

定義

[編輯]

如果圖的任意一個真子圖,其色數均滿足,則稱色臨界圖(英語:-critical graph)。[1]

相關定義

[編輯]

圖染色數

[編輯]

對於給定的圖,存在種顏色和一種染色方案,將圖中每一個頂點都染成種顏色中的一種。如果染色方案滿足一下條件,那麼將稱該染色方案為恰當的染色方案:對於圖中任意兩個頂點,如果,那麼所染成的顏色不同。

對於圖,如果存在一個種顏色的恰當染色方案,我們稱染色的。在所有滿足條件的,稱最小的那個

子圖

[編輯]

對於任意一個圖,如果並且,則稱的子圖,記為。若,則稱的真子圖,記為

葉(lobe)

[編輯]

對於圖即其一個點的子集有連通分支。對任意,我們稱中的導出子圖-葉(-lobe)。

基本性質

[編輯]
  1. 是一個沒有孤立點的色臨界圖,當且僅當對任意
    證明:""由定義可知顯然。"":由於。所以
  2. 設G是一個-色臨界圖,則對任意,存在一種使用種顏色的恰當的染色方式使得種顏色均出現在鄰域英語Neighbourhood (graph theory)中。
    證明:由於色臨界圖的定義知,。所以存在一種使用前種顏色對的恰當的染色方式。然後再對進行染色,則必須有種顏色均出現在中,否則可以用前種色中沒有在出現的顏色對染色,那麼就得到用前顏色對染色的方法,與矛盾。
  3. 設G是一個-色臨界圖,則對任意,任意使用種顏色對的恰當的染色方式均將兩端點染成相同顏色。
    證明:如果存在一種使用種顏色對的恰當的染色方式使得兩端點染成不同顏色,那麼這種方式同樣能對使用,這樣與矛盾。

相關定理

[編輯]

狄拉克定理

[編輯]

任意一個-色臨界圖均為-邊連通英語k-edge-connected graph的。[1]:211

證明用到以下引理:

凱南(Kainen)引理

[編輯]

的最小染色數,並且是對的一個劃分。如果導出子圖均是可染色的,那麼中至少有條邊。[1]:211

證明:

由於均是可染色的,可以把劃分為個獨立集,把劃分為獨立集。如果之間邊少於條,則對進行染色。先對中的點染上種顏色。再分別對逐獨立集染色,並且染每個獨立集時,與其相鄰以及染完色的獨立集個數少於個,所以可在中顏色中選擇餘下某種對其恰當染色。這樣就對使用種顏色恰當染色,與矛盾。引理證明完畢。

回到原證明,如果不是-邊連通的。那麼存在條邊使得不是連通圖,取其一個連通分支,令。由於不連通性可知的邊皆屬。又是色臨界圖,有,所以均是可染色。利用凱南引理可知,的邊數至多是,但,矛盾。

定理2:

[編輯]

如果-色臨界圖,那麼割集英語Cut (graph theory)均不是。特別說明的是,如果有一個割集含有兩個點,那麼並且存在一個-葉使得[1]

參考內容

[編輯]
  1. ^ 1.0 1.1 1.2 1.3 Douglas B.West. Introduction to Graph Theory. Pearson Enducation. : 210–220. ISBN 81-7808-830-4.