雙外平面圖的點染色.pdf

1、圖染色問題是圖論研究中的重要問題之一和熱點之一，有重大的理論價值和應用背景。雙外平面圖是一種新的特殊的平面圖，所有點出現(xiàn)在兩個面的邊界上的平面圖，稱為雙外平面圖。但到目前為止，關于這一特殊的平面圖的很多問題還有待解決，本論文主要雙外平面圖的點染色問題。G的一個k頂點染色是指k種顏色1，2，……，k對于G的各頂點的一個分配，使G為k可染色的數(shù)k的最小值，稱為圖G的點色數(shù)χ(G)。 本論文在參考了雙外平面圖已有結(jié)果的基礎上考慮雙外平

2、面圖的點染色的問題，具體做了以下工作： 1.討論了Δ=2、Δ=3時，χv=2和χv=3。 2.Δ=4時，(1)圖G中有1個圈及剖分點的點色數(shù)，得到(Ⅰ)當頂點總數(shù)為6n時，不管加幾個剖分點，都有χv=3。(Ⅱ)當頂點總數(shù)為6n+2時，加一個剖分點，都有χv=3，加2個及以上剖分點時，剖分點加在標號為2對應的邊上時，有χv=3；剖分點加在標號為1，3對應的邊上時，有χv=4(Ⅲ)當頂點總數(shù)為6n+4時，加一個剖分點，都有χ

3、v=3，加2個及以上剖分點，剖分點加在標號為3對應的邊上時，有χv=3；剖分點加在標號為1，2對應的邊上時，有χv=4。(2)圖G中有1條路及剖分點的點色數(shù)，得到(Ⅰ)不加剖分點時，當頂點數(shù)為{(6n+1)(6n+2)(6n+3)(n-1,2,…)時，χv=4其他情況時，χv=3(Ⅱ)當χv=4時，當在相同面上兩端的頂點標號沖突時，如果剖分點加在這個標號相對的邊上時，仍然有χv=4，加在其他邊上時，有χv=3。(3)圖G中有2條路及剖分