滿足某些特殊條件的平面圖邊染色問題研究.pdf

1、本文討論的圖均為簡單無向有限的平面圖。對于一個圖G=G(V(G)，E(G))，V(G)，E(G)分別表示其頂點集合和邊的集合。對于頂點v∈V(G)，我們用d(v)表示其度數(shù)，△(G)和δ(G)分別表示G中頂點的最大度和最小度，簡記為△和δ。在圖論符號中我們常略去字母G分別用V，E，v和ε代替V(G)，E(G)，v(G)，ε(G)。
　　 圖的染色問題，是圖論的主要研究問題之一。圖的染色一般分為邊染色、點染色、全染色以及其它特定染

2、色。本文討論了平面圖的邊染色問題，證明了兩個主要結(jié)論。
　　 圖G的一個k-邊正常染色是指k種顏色在E(G)上的一種分配，使得相鄰的兩條邊染以不同的顏色。若圖G有一個k-邊正常染色，則稱G是k-邊可染色的。圖G的邊色數(shù)是指使G為k-邊可染色的最小值k，記為x'(G)。
　　 邊染色問題有下面的著名定理：
　　 Vizing定理(1964)設(shè)G是無環(huán)的非空簡單圖，則△(G)≤x'(G)≤△(G)+1。
　　

3、 對于有重邊的圖G，設(shè)μ(G)表示G中邊的最大重數(shù)，Vizing定理實際上證明了一個更一般的結(jié)論：△(G)≤x'(G)≤△(G)+μ(G)。
　　 Vizing定理提出了圖的一個分類問題：若圖G滿足x'(G)=△(G)，則稱G為第一類圖；若圖G滿足：x'(G)=△(G)+1，則稱G為第二類圖。確定一個圖屬于第一類還是第二類是很困難，目前僅對少量圖判明了它們所屬的類。路、樹、二部圖、偶數(shù)階完全圖，輪圖都是第一類圖；奇圈、奇數(shù)階完全

4、圖都是第二類圖。一般情況下一個圖屬于第幾類圖，尚沒有好的充分必要的判別條件。已經(jīng)知道存在最大度是2、3、4、5的第二類平面圖，且Vizing(1965)已證明：不存在最大度≥8的第二類平面圖。Sanders and Zhao[1]證明了最大度為7的平面圖是邊染色第一類圖。目前尚不知道是否存在最大度為6的第二類平面圖。
　　 在本文中我們主要研究平面圖的邊染色問題，其中短圈是指長度小于等于5的圈。我們通過對頂點和面上的值進行重新分