圖的幾類染色問題.pdf

1、圖論是離散數(shù)學(xué)的骨干分支，它不僅具有重要的理論意義，而且具有重要的實際意義，它在管理科學(xué)、計算機科學(xué)與技術(shù)、通信工程等領(lǐng)域都有廣泛的應(yīng)用.圖論的研究始于200多年前，Euler用圖論的方法解決了格尼斯堡七橋問題.自二十世紀(jì)五十年代以來，由于計算機科學(xué)的迅速發(fā)展，有力地推動了圖論的發(fā)展，關(guān)于圖論方面的結(jié)果大量涌現(xiàn).四色猜想作為圖的染色問題的起源，一直引領(lǐng)著圖論的發(fā)展，并使得圖的染色理論成為圖論中的一個重要分支.本文主要討論圖的幾類染色問題

2、，包括圖的均勻染色和均勻可選擇性、列表染色及鄰和可區(qū)別的邊染色等.
　　 本文所研究的圖均為簡單圖，文中我們用V(G)，E(G),δ(G)和△(G)分別表示圖G的點集、邊集、最小度、最大度.對于任意的υ∈V(G)，符號dG(υ)表示圖G中與點υ相關(guān)聯(lián)的邊的條數(shù)，稱為點υ在圖G中的度，簡記為d(υ).令S是一個集合，符號|S|表示集合S中所含元素的個數(shù).對于任意的實數(shù)x，符號[x]和[x]分別表示不小于x的最小整數(shù)和不大于x的最大

3、的整數(shù).符號ad(G)表示圖G中所有點的度數(shù)的平均值，即ad(G)=∑υ(ε)V(G)d(υ)/|V(G)|，稱為圖G的平均度.符號mad(G)表示圖G的所有子圖的平均度的最大值，稱為圖G的最大平均度.如果圖G的所有點的度數(shù)都為κ，則稱圖G為κ-正則圖.如果圖G的任何子圖都含有一個度數(shù)不超過d的點，則稱圖G為d-退化圖.長度為κ的圈稱為κ-圈.長度為3的圈又稱三角形.令C為圖G的一個κ-圈，如果存在邊xy∈E(G)-E(C)，則稱圈C為

4、帶弦的κ-圈.我們稱圖G中所含的最小的圈的長度為圖G的圍長，記為(g)(G).如果我們能將一個圖G畫在一個平面上，使得圖G的任何兩條邊僅在頂點處相交，則稱圖G是可平面的，并稱圖G的這種畫法為它的平面嵌入.方便起見，我們稱一個可平面圖的平面嵌入為平面圖.一個平面圖G將一個平面分割成很多小的區(qū)域，稱每一個小的區(qū)域為圖G的面.符號F(G)表示圖G的所有面的集合.
　　 下面我們簡單介紹一下本文所研究的幾類染色的概念.圖G的均勻染色是一

5、種特殊的點染色.如果圖G的點集V(G)可以劃分成κ個獨立的子集V1，V2，…，Vκ，使得||Vi|-|Vj||≤1（1≤i，j≤κ），則稱圖G是均勻κ-可染的.使圖G能夠均勻κ-可染的最小正整數(shù)κ，稱為圖G的均勻染色數(shù)，記為(χ)e(G).如果(χ)e(G)=κ，且對于任意的l＞κ，圖G是均勻l-可染的，則我們稱κ為圖G的均勻染色數(shù)的界，記為(χ)*e(G).對圖G的每個點υ∈V(G)給定一個相應(yīng)的顏色集合記為L（υ），如果存在圖G的一

6、個正常點染色c，使得對于任意的點υ，都有c（υ）∈L（υ），則稱圖G是列表L-可染的.給定一個顏色列表L,如果對于任意的點υ，都有|L(υ)|=κ，則稱L為κ-一致列表.如果對于任意κ-一致列表L,圖G是列表L-可染的，并且每種顏色所含的點數(shù)不超過「|V(G)|/κ」，則稱圖G是均勻κ-可選擇的.
　　 圖G的列表邊和列表全染色是邊染色和全染色的一種推廣.對圖G的每個元素x∈E(G)∪V(G)給定一個相應(yīng)的顏色集合記為L(x)，

7、稱L={L(x)|x∈E(G)∪V(G)}為圖G的一個全列表.若圖G存在正常全染色c使得對于任意的元素x∈E(G)∪V(G)，都有c(x)∈L(x)，則稱G是列表全L-可染的.給定一個顏色列表L,如果對于任意的元素x∈E(G)∪V(G)，都有|L(x)|=κ，則稱圖G是全κ-可選擇的.使圖G存在全κ-可選擇的最小正整數(shù)κ稱為G的列表全色數(shù)，記為(χ)"l(G).列表邊色數(shù)的定義類似與列表全色數(shù)的定義，所不同的是僅考慮對圖G的邊進行染色，

8、這里不再重述.
　　 圖G的鄰和可區(qū)別的邊染色是一種特殊的邊染色.圖G的正常[κ]-邊染色，是利用顏色集[κ]={1，2，…，κ}的圖G的一個正常邊染色.如果一個正常邊染色使得對于圖G的任意一條邊uυ∈E(G)，都有與點u關(guān)聯(lián)的邊上的顏色數(shù)之和不等于與點υ關(guān)聯(lián)的邊上的顏色數(shù)之和，則稱它為鄰點可區(qū)別的[κ]-邊染色.符號ndi∑(G)表示使圖G具有鄰和可區(qū)別的[κ]-邊染色的最小顏色數(shù)κ.
　　 本文主要討論圖的均勻染色，

9、均勻可選擇性，列表邊染色，列表全染色，鄰點可區(qū)別的邊染色，分四章進行討論.
　　 第一章，我們首先介紹了一些圖論中的概念，術(shù)語和定義;然后，給出了本文所要討論的幾類染色的提出及研究進展;最后，我們給出了本文所要介紹的主要結(jié)論.
　　 第二章，我們討論了圖的均勻染色和均勻可選擇性.我們研究了平面圖，改進了Bu等人在文章[20，57，68，85，91，92]中的關(guān)于平面圖的結(jié)果，得到了一系列更好的結(jié)果;我們還研究了具有最大平