平面圖的點(diǎn)染色.pdf

1、圖G的一個(gè)正常頂點(diǎn)染色是指k種顏色1，2，…，k對(duì)于G的各頂點(diǎn)的一個(gè)分配，使得任意兩個(gè)相鄰的頂點(diǎn)分配以不同顏色。若圖G有一個(gè)正常k-點(diǎn)染色，那么就稱圖G是k-點(diǎn)可染色的。圖G的色數(shù)是指G有一個(gè)正常后頂點(diǎn)染色的數(shù)k的最小值，用χ(G)表示。 圖G的一個(gè)頂點(diǎn)色列表L是一個(gè)顏色集合簇，它指定G的每個(gè)頂點(diǎn)υ一個(gè)顏色集合L(υ)．若G有一個(gè)正常的頂點(diǎn)染色π，使得對(duì)每一個(gè)頂點(diǎn)υ∈ V，有π(υ) ∈L(υ)，則稱G為L(zhǎng)-頂點(diǎn)可染的或者稱π是

2、G的一個(gè)L-染色。若對(duì)每一個(gè)滿足|L(υ)|≥k，υ∈ V的L,G都是L-點(diǎn)可染的，則稱G是k-點(diǎn)可選擇的，簡(jiǎn)稱G是k-可選擇的。G的頂點(diǎn)列表色數(shù)是使得G是k-可選擇的最小的非負(fù)整數(shù)后。 假若染色π是圖G的正常頂點(diǎn)染色，并且對(duì)于G中的任何一個(gè)圈子圖C都應(yīng)用至少3種顏色，那么我們稱染色π是G的一個(gè)無圈染色。圖G的無圈色數(shù)χa(G)就是使得G是無圈k-可染的最小的非負(fù)整數(shù)k。若G有一個(gè)正常的無圈染色π，使得對(duì)每一個(gè)頂點(diǎn)υ∈ V，都有

3、π(υ)∈ L (υ)，則稱G是無圈L-可染的或者稱π是G的一個(gè)無圈L-染色。若對(duì)滿足|L(υ)|≥k，υ∈ V的色列表L,G都是無圈L-可染的，那么稱G是無圈k-可選擇的。G的無圈列表色數(shù)χ<'l><,a>(G)是使得G是無圈k-可選擇的最小的非負(fù)整數(shù)k。 1976年，對(duì)于平面圖的正常頂點(diǎn)著色，Steinberg提出猜想：每個(gè)不包含4-圈和5-圈的平面圖是3-可染色的。 2002年，Borodin等人首次研究了平面圖的

4、無圈L-染色問題，并且在文獻(xiàn)[2]中證明了每個(gè)平面圖都是無圈7-可選擇的。與此同時(shí)，他們還在此文獻(xiàn)中提出了一個(gè)更具有挑戰(zhàn)性的猜想：每個(gè)平面圖都是無圈5-可選擇的。 本學(xué)位論文主要圍繞這兩個(gè)猜想，對(duì)一些平面圖類展開研究。 在第一章中，給出本文所用到的基本概念，簡(jiǎn)述了相關(guān)領(lǐng)域的研究現(xiàn)狀以及呈現(xiàn)了本文的主要結(jié)果。 在第二章中，證明了以下兩個(gè)結(jié)果： (1).每個(gè)不包含{4，6，7，9}-圈的平面圖是3-可染色的；