關(guān)于可平面圖的邊剖分的若干結(jié)果.pdf

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

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

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

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

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

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

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

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