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

1、這篇論文是一篇關(guān)于頂點著色綜述性的文章。 對圖G(V,E)的一種著色是一個標號映射c:V→S,使得(∨) VW∈E(G),c(v)≠c(w).一個k-colouring是在頂點集V上的一個由k個色類構(gòu)成的劃分,使得在同一色類中的點不相鄰。使得圖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)。如果對圖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)于頂點著色的基本概念,一些著色參數(shù)的基本性質(zhì),簡略地討論了著色參數(shù)與圖的結(jié)構(gòu)的關(guān)系,最后一節(jié)是研究的進展和本文的主要結(jié)論。 第二章找出例圖使得ch(G)>x(G)或ch(G)=x(a),介紹了Woodal l,Gravier和Maffray關(guān)于相等的猜測。給出了使得G是n-choosable的與kernel有關(guān)的充分條件,而且進一步指出線圖是可解的當且僅當它是完美的,二部多重圖的線圖是可解的。 第三章介紹了

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

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