圖的幾類染色問(wèn)題.pdf

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

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

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

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

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

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

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

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

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