基本介紹
色數及色數多項式,獨立集與覆蓋之間有密切的關係,
色數及色數多項式
定義：為、設圖G=<V,E>，S V(G)。如果S中的任意兩個頂點在G中均不鄰接，則稱S是一個獨立集。
獨立集S稱為最大的，如果不存在S’，使|S’|>|S|。最大獨立集中頂點的個數稱為G的獨立數，記作α0(G)。
例如，要左圖中，集合{v2, v4,}、{v2, v6,}、{v2, v4, v6,}均為獨立集。
集合{v1, v3,}中的頂點不鄰接，但它們與圖的其他頂點鄰接。但{v1, v3,}不是最大獨立集，集合{v2, v4, v6,}是最大獨立集。
獨立集與覆蓋之間有密切的關係
定理：設S V(G)，S是G的獨立集若且唯若V(T)\S是G的一個覆蓋。
推論：對於p階圖G，有α0+β0=p
9.2頂點著色
定義：用n種顏色對圖的頂點進行著色，且沒有相異的鄰接頂點著相同顏色，則稱為G的一個n-頂點著色，n-頂點著色常簡稱為n-著色
定義：使圖G為n-著色的最小數值G的色數。記作=n，則G為n-色的。
右圖給出一個3-著色圖，我們分別用c1, c2, c3代表三種不同顏色。
顯然，具有任何一種相同顏色的所有頂點的集是獨立的。因此，圖G的一個n-著色是把V(G)分成n個（可能有空的）獨立集的一個劃分。據此，下面的定理和、是顯然的。
定理： χ(G)=1若且唯若G是零圖。
定理：χ(Kn¬)=n。
定理：圖G是2-著色若且唯若G是二部圖。
定理：奇圈和奇階輪圖的色數均為3，而偶階輪圖的色數為4。
定理：對任意圖G，有χ(G) ≦△(G)+1，其中△為G中頂點的最大度。
證明：用歸納法。設|V(G)|=n，顯然，當n=1時，△(G)=0，χ(G)=1。定理成立。
假設定理對頂點個數n=k(k≧1)時命題成立，當n=k+1時，證明如下：設v是G的任一頂點，令G’=G-v，則G’的階數為k，由歸納假設可知，χ(G’) ≦△(G’)+1≦△(G)+1。
當將G’還原成G時，由於v至多與G’中△(G)個頂點相鄰，而在G’的點著色中，△(G)個點至多用△(G)種顏色，於是在△(G)+1種顏色中至少存在一種顏色給v著色，使得v與相鄰頂點塗不同顏色。
定理：連通圖G不是完全圖Kn(n≧3)，也不是奇圈，則χ(G)≦△(G)。
例：求圖所示各圖的色數。
