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

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

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

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

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