有關(guān)平面圖的邊面染色的若干結(jié)論.pdf

1、本文只研究有限簡單無向平圖.設(shè)G是一個平圖，V(G)，E(G)，F(xiàn)(G)分別指G的點(diǎn)集，邊集，面集.設(shè)EF(G)=E(G)∪F(G).若uv∈E(G)，則稱u和v相鄰.頂點(diǎn)v的度指與v相鄰的頂點(diǎn)的數(shù)目.用δ(G)和Δ(G)分別表示(頂點(diǎn))的最大度和(頂點(diǎn))的最小度.使得任兩相鄰或相連元素得以分配不同的顏色的E∪F的一個染色稱為平圖G的邊面染色.平圖G的每一個邊面染色所需的最少色數(shù)叫做G的邊面染色數(shù)，記作χef(G). 1975年

2、，Melnikov曾經(jīng)猜測：對于任何一個平圖G有Δ(G)≤χef(G)≤Δ(G)+3.Waller(SandersandZhao)分別獨(dú)立地用四色理論證明了這個猜想.在2002，Wang和Lih未用四色定理證明了此猜想.在1994，Borodin證明了：對任何平面圖G，Δ(G)≤χef(G)≤max{11，Δ(G)+1}.在1995，Wang證明了：對任何外平面圖G，有Δ(G)≤χef(G)≤max{7，Δ(G)+1}，如果G是2-連通

3、的且Δ(G)≥6，則χef(G)=Δ(G).在1999，Wang和Zhang進(jìn)一步改進(jìn)了Wang的結(jié)果，確定了Δ(G)≥5的外平面圖的邊面染色數(shù).在2005和2007，Wu和Wang把上面的結(jié)果推廣到了系列平行圖上，得到了：如果G是2-連通的Δ(G)≥5的系列平行圖，則χef(G)=Δ(G). 本文證明了下面的結(jié)果. 定理1設(shè)m(m≥6)是一個整數(shù)，G是Δ(G)≤m的Halin擴(kuò)展圖.則G存在色為1，2，…m的一個m色的

4、邊面染色σ使得σ(fo)=1，和對于任意的頂點(diǎn)v∈V(fo)，令e，e1，e2是與v關(guān)聯(lián)的3條邊，有|{σ(e1)，σ(fe1)，σ(e2)，σ(fe2)}|≥3，其中{e1，e2}(∈)E(fo). 推論2對任何Δ(G)≥6的Halin圖或Halin擴(kuò)展圖G，有χef(G)=Δ(G). 定理3設(shè)m(m≥5)是一個整數(shù)，G是Δ(G)≤m的Halin圖.則G存在色為1，2，…，5的一個m色的邊面染色σ，使得(1)σ(fo)

5、=1，(2)對于任意的邊e∈EG(fo)，{σ(e)，σ(fe)}(∈){2，3，4，5}，(3)對于任意的頂點(diǎn)v∈V(fo)，令e，e1，e2是與v關(guān)聯(lián)的3條邊，其中{e1，e2}(∈)E(fo)，有|{σ(e1),σ(fe1),σ(e2)σ(fe2)}|={(3,如果σ(e)≠1)(4,其他情況.)定理4Δ(G)=4的Halin圖G，有χef(G)=5. 推論5Δ(G)=3的Halin圖G，有4≤χef(G)≤5。

6、定理6設(shè)m(m≥6)是一個整數(shù)，G是Δ(G)≤m的雙圈樹圖.則G存在色為1，2，…m的一個m色的邊面染色σ使得(1)σ(fo)=σ(f1)=1，和(2)對于任意的頂點(diǎn)v∈V(fo)，令e，e1，e2是與v關(guān)聯(lián)的3條邊，有|{σ(e1)，σ(fe1)，σ(e2)，σ(fe2)}|≥3，其中{e1，e2}(∈)E(fo)。 定理7假設(shè)G是Δ(G)=3的二連通平圖，則χef(G)=Δ(G)的充分必要條件是G是一個2-連通3-正則二分平