關于可平面圖的邊剖分的若干結果.pdf

1、本文考慮的圖若無特殊聲明均為簡單、無向有限圖。對于一個圖G=G(V(G)，E(G))，本文用V(G)和E(G)分別表示圖的頂點集合和邊集合。對任意的ν∈V(G)，采用d<,G>(ν)表示頂點ν在G中的度數(shù)?！?G)和δ(G)分別表示圖G的最大度和最小度。對V(G)的子集S，用G-S表示從G中刪去頂點集合S及其關聯(lián)的邊所得到的子圖。若S={ν}，則令G-ν=G-{ν}。對E(G)的子集x，用G-X表示從G中刪去邊集合X所得的子圖。若X={

2、e}，則G-{e}簡記為G-e。若存在V(G)的兩個不交子集X、Y，使得V(G)=X ∪Y，且G的所有邊均一個端點在X內，另一個端點在Y內，則稱G為二部圖，記為G=(X，Y，E(G))。 若圖G可以表示在平面上，并且任兩條邊僅在其端點處才可能相交，則稱G是可平面圖。圖G的這種平面上的表示法稱為G的一個平面嵌入，或稱為平面圖。對于一個平面圖G，我們用F(G)來表示G的面集合。對于一個面f，我們把將f圍起來的所有的邊所構成的集合稱為

3、f的邊界，并且稱f關聯(lián)于其邊界上的所有的頂點和邊。同樣地，可以定義，的度dG(f)為f的邊界上的邊數(shù)。若G的兩個面f<,1>和f<,2>有一條公共邊e，則稱面f<,1>和f<,2>相鄰接于邊e。若存在映射φ：E(G)→{1，2，…，κ}，對于G中任意兩條相鄰接的邊e<,1>和e<,2>，滿足φ(e<,1>)≠φ(e<,2>)，則稱G是κ一邊可染色的。這時對于任意的1≤i≤κ，φ<'-1>(i)的邊導出子圖均是圖G的一個匹配。我們把使得圖

4、G具有κ-邊染色的最小正整數(shù)κ定義為G的邊染色數(shù)，記作X(G)。 若圖的每一個連通分支都是一條路，則稱該圖為一個線性森林。我們稱映射ψ：E(G)→+{1，2，…，t)為圖G的一個t-線性染色，如果對于任意的1≤α≤t都有，ψ<'-1>(α)的邊導出子圖是一個線性森林。本文把使圖G具有t-線性染色的最小正整數(shù)t稱為G的線性蔭度，記作lα(G)。 圖的染色理論是圖論的一個重要分支，是圖論研究中最活躍的課題之一。根據(jù)一定的規(guī)則

5、將一組目標劃分為不同的種類，這是數(shù)學中的一個基本方法。不同的規(guī)則決定著該組中任意一對目標是否在同一個類中。圖的染色理論就是研究這類問題的一門理論，它有著相當廣泛的應用背景。各種形式的日程表問題，時間表問題以及排序問題，從根本上來說都可以歸結為染色問題。對染色理論的研究最早可以追溯至1852年，即著名的“四色猜想”的提出。而圖的邊染色問題引起人們關注的時間相對較晚。但是，許多研究領域，如地圖染色，匹配理論以及拉丁方，都與邊染色問題有著緊密

6、的聯(lián)系。關于邊染色的第一篇文章出現(xiàn)在1880年，由P.G.Tait在對“四色猜想”做進一步的研究時，證明出“任一2-邊連通，3-正則的甲面簡單圖是3-邊可染色的”與“四色猜想”足等價的。此后，關于邊染色問題的研究又有了一些比較重要的結論，如Konig's Theorem，Shannon's Theorem以及Vizing's Theorem。圖的邊染色中，根據(jù)著名的Vizing's Theprem，可以將簡單圖分為兩類。圖的分類問題就是

7、判斷一個圖G究竟是第一類圖，還是第二類圖的問題。關于圖的分類問題，雖然已有一些相關的結論，但是未解決的部分還有很多。而對于可平面圖的邊染色的分類問題，Vizing證明出任一△(G)≥8的可平面圖G均是第一類圖，而△∈{2，3，4，5}的可平面圖中存在第二類圖。于是Vizing在1968年的時候，提出了著名的可平面圖猜想。 圖G的線性蔭度這一概念是由Harary在1970年提出的。接著在1980年，由Akiyama，Exoo和Ha

8、rary等人給出了關于正則圖的線性蔭度的猜想；并且在這一猜想的基礎上，產生了著名的線性蔭度猜想(the Linear Arboricity Conjecture，簡稱為LAC)。在對線性蔭度猜想進行研究時，J.Wu解決了可平面圖條件下這個猜想的大部分情況，只余下△=7這一種情況仍未解決。 本文中主要研究的是可平面圖的邊染色及線性蔭度方面的一些結果。 全文共分三章，第一章簡單介紹一下圖論中的一些基本概念，并給出邊染色、線性