色數

頂點着色：設圖

，我們使用n種顏色對V中的每個頂點進行着色，如果滿足沒有相鄰頂點着相同顏色， 則稱其為G的一個n-頂點着色，n-頂點着色常簡稱為n-着色。 ^[3] 

k-可着色：對於圖G，如果存在一個G的k-頂點着色，則我們稱圖G為k-可着色。 ^[4] 

色數：對於整數k，如果G為k-可着色，且不存在正數k’，

且滿足G為k'-可着色，則我們稱k為G的色數（最小着色數），通常用

來表示。 ^[2] 

如圖1，是對Petersen圖的一種着色。觀察可發現，所有相鄰頂點均為不同顏色，所以這是一個Petersen圖的一個3-頂點着色，且Petersen圖為3-可着色。注意，Petersen圖的色數

也是3，因為Petersen圖不可2着色。

1- 對於

, |G|=N,

證明：

G的頂點數為N，用N種顏色對其頂點着色使得每個頂點顏色均不相同，必然可以保證相鄰頂點不同色。

當G的N個頂點全都不連通時，可全部用同一種顏色着色。所以，

。

2-

，

是完全圖

證明：

充分性：如果G是完全圖，

，即任意兩頂點相鄰，所以任意兩個頂點必須着不同顏色，

.

必要性：我們假設存在G，G不是完全圖，且

。由於G不是完全圖，

.我們設u的着色c(u)，v的着色為c(v)。由於u,v並不相鄰，且u和v的顏色與其它頂點的顏色均不相同，我們可以令c(v)=c(u),即給v着u的顏色。這樣依然可以保證相鄰頂點不同色，所以

，產生矛盾。所以如果

，G必須是完全圖。

3- G=，

定義了圖G中最大完全子圖的大小，

證明：

由於完全圖的色數等於它的頂點數，對於G中的完全子圖，至少需要其完全子圖大小數量的顏色才能進行着色。所以

。

4-

，

為G中頂點度的最大值，

證明：

由定義可知，

,

。採用

種顏色，對於每個頂點v，我們都可以讓它自己和所有鄰居點全部採用不同的顏色。這樣就可以產生一種正確的着色方式。

5-

，G為二部圖當且僅當

證明：

必要性：當G為二部圖時，G可以分為兩個部分

和

，且

和

內部的點無邊相連。所以我們可以直接為

和

中的點分別賦予不同的顏色。

充分性：

圖中不存在長度為奇數的圈。假設圖中存在長度為奇數的圈

,2種顏色一定無法着色。由於相鄰點無法着相同的顏色，我們令

,

為兩種不同的顏色。最終

和

也會是相同的顏色，但它們是相鄰的點。所以如果圖中存在長度為奇數的圈，

。即

圖中不存在長度為奇數的圈

為二部圖。

6-

，G為連通圖且G既不是長度為奇數的圈也不是完全圖，那麼

。

證明：

設|G|=n,

。由於G不是完全圖，所以

. 當k=2, G一定是一條路徑或者是一個長度為偶數的圈，易知

. 假設k

。我們設

,並且利用貪心算法分下列三種情況進行着色，證明

.

情況1：假定G不是k-正則圖，即不是所有點的度均為k。這樣一定存在一個點u，

。我們令這個點為

,

,

表示

的鄰居點。同樣地，對於任意i,

由於G有有限個點，所以最終會停止，圖示見圖2.

下面我們為這些集合中的點進行編號。

中的點編號為

,

中的點編號為

。一直這樣知道所有的點都被成功編號。下面我們按照編號從

到

依次進行着色。對於任意一個

（

）,u必然有一個鄰居點在

中，所以編號在u之前的鄰居點的個數至多隻有k-1個，至多隻會佔用k-1種顏色，那麼我們一定可以採用一種沒有佔用過的顏色對u進行着色。如果

,由於u為我們找到的度小於k的點，所以它已着色的鄰居點個數依然小於k，我們仍舊可以給u着色。按照這種模式，我們可以採用不超過k種顏色對所有點進行着色。

情況2：假設G是一個k-正則圖並且G有一個割點v，如圖3。由於v為G的割點，刪去v必然造成G的不連通性。我們假設刪去v後產生的連通分支為

。圖

(i=1,2,...,t). 考慮圖

，v在

中的度小於k，那麼在

中我們可以使用情況1中的方法進行採用不超過k種顏色進行着色。同理，在所有

中均可以採用這種方法進行着色，我們可以假定在所有

中v的顏色都相同（如果不相同，直接交換顏色即可）。最終，對於所有G中的點，我們都可以用不超過k種顏色進行成功着色。

情況3：假設G是一個k-正則圖且G中沒有割點，所以G的割點集的大小大於等於2。

3.1 G的最小割點集的大小大於2，那麼刪去任意兩個點，G依然是連通的。我們選取一個點u，

為它的兩個鄰居點，且

。我們一定可以找到這樣的三個點，否則G就是一個完全圖。我們還知道，

是連通的。

3.2 G的最小割點集的大小為2。那麼存在一對點v,w，

是不連通的。我們設定G-{v,w}的連通分支為

。由於

,任意

至少含有兩個點，v至少連通了

中的一個點。我們假定

且u是v的鄰居點。如果u是圖G-v的一個割點，那麼

中至少還存在一個點y，滿足y不是G-v的割點，並且y與v相連。我們把這個與v相連且不是G-v割點的點記為

。同理，在

中，我們可以找到這樣的點

。

在這兩種情況下，我們都可以找到點

，滿足

且

是連通的。接下來我們可以利用貪心算法對圖進行着色。

首先將找到的點

分別編號為

。接下來我們找到一個

的鄰居點，該鄰居點不是

(這樣的點必然可以找到，因為

)，我們將這個點編號為

。接下來再找一個

或

的未編號鄰居點，編號為

。我們一直重複這個過程，直到所有點都成功編號。由於

是連通的，對於任意

。

編號完成後，我們可以利用貪心算法按順序從

到

開始編號。由於

，我們可以給它們賦予同樣的顏色。對於

，它最多隻有k-1個編號在前的鄰居點，最多佔用k-1種顏色，一定可以賦予一種新的顏色。對於

，由於它有兩個鄰居點

着同一種顏色，其k個鄰居點也至多佔用k-1種顏色，依然可以着色。所以，所有點都可以用k種顏色進行着色。

對於以上三種情況，均可以用k種顏色進行着色，所以

。

6- 奇圈和奇階輪圖的色數均為3，而偶階輪圖的色數為4。

獨立集定義：圖

，

，如果S中的任意兩個頂點在G中均不鄰接，則稱S是一個獨立集。 ^[5] 

獨立數：對於獨立集S，如果不存在S’，使

，S稱為最大獨立集。S種頂點的個數成為G的獨立數，記為

。 ^[5] 

定理：設

，S是G的獨立集當且僅當

是G的一個覆蓋。

推論：對於p階圖G，有

色數與獨立集：具有任何一種相同顏色的所有頂點的集是獨立的，因為相同顏色的點必定不是鄰接點。因此，圖G的一個n-着色是把V(G)分成n個（可能有空的）獨立集的一個劃分

色數與獨立數滿足：

, |V|=n,

證明：

由於G的一個n着色可以看作是將V(G)分成n給獨立集的劃分，設

,我們可以將G分為k個獨立集

。根據獨立集的定義，

。所以

.

由於k為G的一個最小劃分，

所以

.