唯一頂點(diǎn)著色、唯一列表著色的整體結(jié)構(gòu)與其著色參數(shù)的關(guān)系的討論.pdf

1、這篇論文是一篇關(guān)于頂點(diǎn)著色綜述性的文章。 對(duì)圖G(V,E)的一種著色是一個(gè)標(biāo)號(hào)映射c:V→S,使得(∨) VW∈E(G),c(v)≠c(w).一個(gè)k-colouring是在頂點(diǎn)集V上的一個(gè)由k個(gè)色類構(gòu)成的劃分,使得在同一色類中的點(diǎn)不相鄰。使得圖G存在k-colouring c:V→{1,…,k}的最小的正整數(shù)k稱為G的chromatic number,記為x(G)。如果圖G的任何k-colouring產(chǎn)生的色類劃分相同,我們稱G

2、是uniquely vertex k-colourable(or a k-UCG)。如果對(duì)圖G的任何list assignment(￡)={L(v):v∈V(G)}且|L(v)|=k,都能選擇到G的著色。我們稱G是k-list-colourable,或k-choosable,使得G是k-choosable最小的正整數(shù)k稱為G的list chromatic number或choosability,記為ch(G)或x1(G)。 第一

3、章主要介紹了關(guān)于頂點(diǎn)著色的基本概念,一些著色參數(shù)的基本性質(zhì),簡略地討論了著色參數(shù)與圖的結(jié)構(gòu)的關(guān)系,最后一節(jié)是研究的進(jìn)展和本文的主要結(jié)論。 第二章找出例圖使得ch(G)>x(G)或ch(G)=x(a),介紹了Woodal l,Gravier和Maffray關(guān)于相等的猜測。給出了使得G是n-choosable的與kernel有關(guān)的充分條件,而且進(jìn)一步指出線圖是可解的當(dāng)且僅當(dāng)它是完美的,二部多重圖的線圖是可解的。 第三章介紹了

4、與n-choosable圖不同的uniquely list colourable圖的性質(zhì),主要介紹了uniquely 2-list colourable圖的性質(zhì),一個(gè)連通圖G是uniquely 2-list colourable當(dāng)且僅當(dāng)它至少有一塊(block)既不是圈,不是完全圖,也不是完全二部圖。一個(gè)連通圖G是uniquely 2-list colourable當(dāng)且僅當(dāng)它至少有一塊(block)既不是圈,不是完全圖,也不是完全二部圖

5、。圖G是uniquely 2-list colourable當(dāng)且僅當(dāng)它是t=max{3,x(G)}的uniquely(2,t)-list colourable。 在第四章的第一節(jié),我們研究構(gòu)造無Kk的k-UCG時(shí),計(jì)算參數(shù)∧(G)的值。首先找出具體的圖說明無Kk的k-UCG的存在性,以此為基礎(chǔ)用逼迫的辦法構(gòu)造k-UCG,而不增加團(tuán)數(shù),給出了計(jì)算∧(G)的公式。在第二節(jié)用uniquely list eolourable圖(G,(￡