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

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

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

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