平面圖的點染色.pdf

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

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

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

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