關(guān)于平面圖的全染色的幾個結(jié)果.pdf

1、對圖論的研究已經(jīng)有二百多年的歷史，最早關(guān)于圖論的文章是在1736年由歐拉完成的，該文章解決了著名的哥尼斯城堡七橋問題.自20世紀(jì)六十年代以來，圖論得到了迅猛發(fā)展，圖論方面的結(jié)果大量涌現(xiàn)，其中圖的染色理論在圖論研究中占有重要的地位，圖的染色理論在最優(yōu)化、計(jì)算機(jī)理論、網(wǎng)絡(luò)設(shè)計(jì)等方面有著重要的應(yīng)用.本文旨在討論平面圖的全染色.
　　本文討論的圖均為簡單無向有限的平面圖.對于一個圖G=G(V(G),E(G),ψG),V(G),E(G)分別

2、表示其頂點(diǎn)集合和邊的集合，ψG為點(diǎn)和邊的關(guān)聯(lián)函數(shù).對于頂點(diǎn)v∈V(G),我們用d(v)表示其度數(shù)，△(G)和δ(G)分別表示G中頂點(diǎn)的最大度和最小度，簡記為△和δ.在圖論符號中我們常略去字母G分別用V,E,v和ε代替V(G),E(G),v(G),ε(G).
　　若圖G可以表示在平面上，并且任兩條邊僅在其端點(diǎn)處才可能相交，則稱G是可平面圖.圖G的這種平面上的表示方法稱為G的一個平面嵌入，或稱平面圖.一個平面圖G把平面劃分為若干個連通

3、區(qū)域，這些區(qū)域的閉包稱為G的面，圖G所有的面構(gòu)成的集合記為F.一個面f∈F所關(guān)聯(lián)的邊的個數(shù)（割邊計(jì)算兩次）稱為面f的度，用d(f)或r(f)表示.若G的兩個面有一條公共邊，則稱這兩個面相鄰.如果G是連通的平面圖，則有｜V｜-｜E｜+｜F｜=2(Euler公式).
　　根據(jù)一定的規(guī)則將一組目標(biāo)劃分為不同的種類，這是數(shù)學(xué)中的一個基本方法.不同的規(guī)則決定著該組中任意一對目標(biāo)是否在同一類中.圖的染色理論就是研究這類問題的一門理論，它有著相

4、當(dāng)廣泛的應(yīng)用背景.各種形式的日程表問題、時間表問題以及排序問題，從根本上來說都可以歸結(jié)為染色問題.
　　圖G的全k染色是指至多用k種顏色，對G的頂點(diǎn)和邊同時染色，使得相鄰的兩個元素（點(diǎn)和點(diǎn)，邊和邊，點(diǎn)和邊）染以不同的顏色.圖G的全色數(shù)xT(G)是指G的全k染色中最小的正整數(shù).如果一個圖G的全色數(shù)xT(G)=△(G)+1，則稱G為第一類圖.對于G的全色數(shù)xT(G)，已有的結(jié)果可以總結(jié)為：
　　（1）對△(G)≠6的平面圖，有x

5、T(G)≤△(G)+2；
　　（2）對△(G)≥9的平面圖，有xT(G)=△(G)+1.
　　本文對平面圖的全染色進(jìn)行了討論.全文共分三章.第一章介紹了圖論中的一些基本概念，綜述了當(dāng)前全染色理論的主要研究成果和本文的一些主要結(jié)果.第二章我們考慮最大度較小的平面圖的全染色.Behzad和Vizing分別對全染色進(jìn)行了研究，提出了下面的猜想：
　　猜想 對任意圖G，都有△(G)+1≤xT(G)≤△(G)+2.該猜想被稱為