幾類圖的雙約束邊染色問題.pdf

1、本文考慮的圖均為簡單無向有限連通圖.一個圖G，若能被畫在平面上，使得其每兩條邊僅在端點(diǎn)處才能相交，則稱它為可嵌入平面的，簡稱可平面的.平面圖的這種在平面上的畫法稱為一個平面嵌入，也稱之為是一個平面圖.一個平面圖G把平面劃分成若干個連通區(qū)域，這些區(qū)域的閉包稱為G的面，其中唯一的一個無界面稱為G的外部面，其它的面均為內(nèi)部面.對于一個平面圖G，我們用V(G)、E(G)和F(G)分別表示圖的頂點(diǎn)集合、邊集合和面集合，兩個面f1，f2∈F(G)，

2、當(dāng)且僅當(dāng)f1和f2有公共邊時稱它們?yōu)橄噜?；面的邊界上的點(diǎn)和邊稱為與該面相關(guān)聯(lián)，與面f相關(guān)聯(lián)的邊的數(shù)目稱為面f在G中的度(割邊計(jì)算兩次)，記為dG(f).G中的面度最大者稱為G的最大面度，記為FM(G)；外部面的面度記為Fext(G)，同時，用Δ(G)、δ(G)分別表示G的頂點(diǎn)的最大度和最小度. 平面圖G的有點(diǎn)面約束的邊染色，也稱雙約束邊染色，是指對G的邊進(jìn)行染色使得關(guān)聯(lián)同一點(diǎn)的邊有不同的顏色且在同一面上的邊也有不同的顏色：使圖G

3、可進(jìn)行雙約束邊染色所需的最小顏色數(shù)稱為G的雙約束邊色數(shù)，記為χe/vf(G).O.V.Borodin和D.R.Woodall首先提出了雙約束邊染色的概念，并針對外平面圖的雙約束邊色數(shù)進(jìn)行了研究，得出了比較好的結(jié)果.本文針對平面圖的雙約束邊染色問題進(jìn)行了進(jìn)一步的廣泛研究，其中重點(diǎn)就若干特殊類型的平面圖，如近似Halin圖、近似外平面圖、雙外平面圖、高度平面圖等，展開了較深入的討論.平面圖G，如果δ(G)≥3且G去掉外部面的邊界之后是一棵樹

4、，就稱為是一個Hailin圖；而一個非Hailin圖如果近去掉或者是收縮一條邊以后就成為一個Hailin圖，我們稱為是一個近似Hailin圖.平面圖G，如果其所有的頂點(diǎn)都在同一個無界面的邊界上，則稱它為一個外平面圖；一個非外平面圖如果近去掉或者是收縮一條邊以后就成為一個外平面圖，我們也稱為是一個近似外平面圖.所有頂點(diǎn)都出現(xiàn)在兩個面上的平面圖稱為雙外平面圖.平面圖G，若滿足Δ(G)=|V(G)|-k，k=1,2，…，則稱G為一個hk-圖，

5、k=1，2的hk-圖稱為高度平面圖，無割點(diǎn)的hk-圖又稱為pk-圖. 全文共分五章，第一章介紹了圖論中的若干基本概念，簡單綜述了圖的染色理論的發(fā)展過程以及與本文相關(guān)的一些已有的結(jié)果.第二章首先介紹了Halin圖的雙約束邊染色已經(jīng)的較好的結(jié)果.然后分別研究了兩類近似Hailin圖(幾乎Halin圖，Halin圖的弱剖分圖)的雙約束邊染色問題.第三章介紹了關(guān)于外平面圖的雙約束邊染色的已有結(jié)果，重點(diǎn)就兩類近似外平面圖(幾乎外平面圖，外

6、平面圖的弱剖分圖)的雙約束邊染色問題展開了研究.第四章介紹了雙外平面圖的特點(diǎn)，研究了特殊的雙外平面圖的雙約束邊染色問題.第五章初步研究了特殊的高度平面圖的雙約束邊染色問題.得出的主要結(jié)論有：定理1設(shè)G是幾乎Halin圖，且余邊e位于G-e的內(nèi)部面上，則有χe/vf(G)=Fext(G).定理2設(shè)G是幾乎Halin圖，且余邊e位于G-e的外部面上，如果G-e非輪圖，且存在有內(nèi)部面達(dá)到了最大面度，則有χe/vf(G)=FM(G).定理3設(shè)G

7、是Halin圖的弱剖分圖，則有χe/vf(G)=FM(G).定理4如果G是帶有余邊e的幾乎外平面圖，而G-e恰是由一個圈加上一條對角線構(gòu)成的外平面圖，那么FM(G)≤χe/vf(G)≤FM(G)+1.定理5如果G是帶有余邊e的幾乎外平面圖，而G-e是Δ=4的2-連通極大外平面圖，那么χe/vf(G)≤max{FM(G)+1，Δ(G)+1}.定理6若G恰好是Cn加上一條k-對角路構(gòu)成(n≥3，k≥1)，則χe/vf(G)=n+k≤3/2F

8、M(G)，且當(dāng)且僅當(dāng)n=2k且對角路為正對角路時，達(dá)到最大值3/2FM(G).定理7假設(shè)G'為2-連通的外平面圖，G為G'的弱剖分圖，只要G不是由一個圈加上一條對角路，就有χe/vf(G)=Fext(G).定理82-連通圖G如果是正則雙外平面圖，那么χe/vf(G)≤FM(G)+1.定理9設(shè)G是|V(G)|≥6的p1類圖，則必有χe/vf(G)≤Δ(G)+1，且χe/vf(G)=Δ(G)+1當(dāng)且僅當(dāng)圖G同構(gòu)于圖5.1.1所示的圖PΔ.