若干三部圖的色唯一性.pdf

1、為了攻克四色問(wèn)題,1912年Birknoff在文獻(xiàn)中介紹了關(guān)于映射M的色多項(xiàng)式,記為P(M,λ),它是在映射M下的正常λ-色數(shù).如果能夠證明對(duì)于所有的映射M都有P(M,4)>0,這就對(duì)四色問(wèn)題給出了一個(gè)肯定的回答.圖G的一個(gè)七頂點(diǎn)著色是指k種顏色1,2,…,k對(duì)于G的各頂點(diǎn)的-個(gè)分配；稱(chēng)著色是正常的,如果兩個(gè)相鄰的頂點(diǎn)都分配到不同的顏色.無(wú)環(huán)圖G的-個(gè)正常k頂點(diǎn)著色是把V分成k個(gè)(可能有空的)獨(dú)立集的一個(gè)分類(lèi)(V1,V2,…,Vk).當(dāng)

2、G有-個(gè)正常k頂點(diǎn)著色時(shí),就稱(chēng)G是k頂點(diǎn)可著色的(簡(jiǎn)稱(chēng)為k可著色).G的色數(shù)x(G)是指使G為k可著色的數(shù)七的最小值；若x(G)=k,則稱(chēng)G是k色的.
　　 圖G的色多項(xiàng)式就是至多用入種顏色對(duì)圖G進(jìn)行正常著色所有可能的不同的方法數(shù),記作P(G,λ).對(duì)于-個(gè)正整數(shù)r,V(G)的-個(gè)分劃(A1,A2,…,Ar)就叫做圖G的-個(gè)r獨(dú)立分劃,如果Ai是圖G的非空獨(dú)立集.α(G,r)表示V(G)的r獨(dú)立分劃數(shù),那么G的色多項(xiàng)式可以寫(xiě)成:

3、這里(λ)i=λ(λ-1)(λ-2)…(λ-i+1).
　　 如果P(G,λ)=P(H,λ),則圖G和H是色等價(jià)的,記為G～H.用表示與G色等價(jià)的所有圖組成的圖族.1978年,Chao和Whitehead在文獻(xiàn)中定義了-個(gè)圖是色唯一的如果沒(méi)有其它圖與它具有相同的色多項(xiàng)式.即:如果與圖G色等價(jià)的圖都與G同構(gòu),則稱(chēng)圖G是色唯一的.
　　 本文主要利用色等價(jià)與色唯一的性質(zhì)以及伴隨等價(jià)和伴隨唯一的性質(zhì)來(lái)研究在完全三部圖K(n,n