某些特殊圖的點(diǎn)染色問題研究.pdf

1、圖論是現(xiàn)代數(shù)學(xué)的重要分支之一，圖的染色問題是圖論中的熱點(diǎn)也是難點(diǎn).圖的染色問題起源于著名的“四色定理”，即給平面上的任何一張地圖著色，使得有公共邊界的國家染上不同的顏色，至多使用四種顏色([1-3])。后來，有些學(xué)者將平面圖的染色問題擴(kuò)展到1-平面圖的染色研究。一個(gè)圖稱為是1-平面的當(dāng)且僅當(dāng)它可以畫在一個(gè)平面上，使得它的任何一條邊最多交叉另外一條邊。1984年，Bordin[4]證明了1-平面圖是6-可染的。1976年，Steinber

2、g[5]提出猜想：不含4-圈和5-圈的平面圖是3-可染的。為了證明Steinberg猜想，學(xué)者把平面圖的正常點(diǎn)染色推廣到非正常點(diǎn)染色，Xu[6]證明了不含4-圈和5-圈的平面圖是(1,1,0)-可染的；Hill[7]證明了不含4-圈和6-圈的平面圖是(3,0,0)-可染的;Xu[8]證明了不含4-圈和6-圈的平面圖是(1,1,0)-可染的；Wang[10]證明了不含4-圈和6-圈的平面圖是(2,0,0)-可染的等等.2011年，Chan

3、g[11]研究了Steinberg猜想并考慮了附近的染色。1986年，L.Cowen[12]提出了圖的缺陷染色。
　　圖G的點(diǎn)染色是對(duì)圖G的頂點(diǎn)集的一種剖分.如果圖G的頂點(diǎn)集V可以剖分成互不相交的k個(gè)部分，給每一部分染上同一種顏色并且使得每部分的生成子圖滿足某種要求。若剖分產(chǎn)生的各部分都是點(diǎn)獨(dú)立集，則為圖G的正常點(diǎn)染色，否則稱為圖G的非正常點(diǎn)染色。如果對(duì)每部分剖分的導(dǎo)出子圖中頂點(diǎn)的度數(shù)做限制,使得G[Vi]中所有頂點(diǎn)的度均不超過忒

4、,則稱圖G是(d1,d2,…,dk)-可染的[12]。圖的色數(shù)是指給一個(gè)圖染色所用的最少顏色數(shù)。如果存在映射Φ:V→(1,…,dk},滿足uv∈E時(shí),Φ(u)=Φ(v),則稱Φ是G的一個(gè)k-染色。若G有一個(gè)k-染色，則稱G是k-可染的。
　　關(guān)于圖的正常點(diǎn)染色，主要有以下結(jié)果：
　?、臶四色定理[3]]平面圖是4-可染的；
　　(2)1-平面圖是6-可染的([4]);
　　(3)[Steinberg猜想叫不含4-

5、圈和5-圈的平面圖是3-可染的；
　　(4)若圖G為平面圖，且不含長度為4,5,6,7的圈，則圖G是3-可染的([13]);
　　(5)若圖G為平面圖且不含長度為4,5,6,8的圈，則圖G是3-可染的([14])
　　(6)若圖G為平面圖且不含長度為4,5,6,9的圈，則圖G是3-可染的([15]);
　　(7)若圖G為平面圖且不含長度為4,5,7,8的圈，則圖G是3-可染的([16]);
　　(8)若圖G

6、為平面圖且不含長度為4,6,7,8的圈，則圖G是3-可染的([17]);
　　(9)若圖G為平面圖且不含長度為4,6,8,9的圈，則圖G是3-可染的([18]);
　　(10)若圖G為平面圖，且不含長度為4,7,8,9的圈，則圖G是3-可染的([19]);
　　此外，Bordin等人在([20-26])中也研究了平面圖的3-可染性。關(guān)于圖的對(duì)每個(gè)剖分中點(diǎn)的度數(shù)做限制的非正常點(diǎn)染色，主要有以下結(jié)果：
　　⑴若圖G為

7、平面圖,且不含4-圈和5-圈，則圖G是(1,1,0)-可染的([6]);
　　(2)若圖G為平面圖，且不含4-圈和5-圈，則圖G是(3,0,0)-可染的([7]);
　　(3)若圖G為平面圖，且不含4-圈和6-圈，則圖G是(1,1,0)-可染的([8]);
　?、热魣DG為平面圖，且不含4-圈和6-圈，則圖G是(2,0,0)-可染的([10]);
　　基于目前對(duì)圖的點(diǎn)染色的研究，本人跟隨前面學(xué)者的腳步，繼續(xù)對(duì)圖的染

8、色問題進(jìn)行研究。
　　在第一章主要介紹了論文中所涉及的一些概念和術(shù)語符號(hào)以及本文的研究背景和已有的一些結(jié)果。
　　在第二章中，我們?nèi)匀豢紤]傳統(tǒng)的正常點(diǎn)染色問題,但我們將平面圖的正常點(diǎn)染色研究推廣到1-平面圖的正常點(diǎn)染色研究。Bordin[4]證明了1-平面圖是6-可染的，本文考慮不含4-圈且5-點(diǎn)不與5-點(diǎn)相鄰的1-平面圖的點(diǎn)染色，得到下面的結(jié)果：
　　定理1.如果圖G是1-平面圖，滿足圖G不包含4-圈并且圖G中5-點(diǎn)

9、不與5-點(diǎn)相鄰，那么圖G是5-可染的。
　　定理1是在1-平面圖的正常點(diǎn)染色中，限制掉圖中的4-圈，滿足5-點(diǎn)不與5-點(diǎn)相鄰，將1-平面圖的正常點(diǎn)染色色數(shù)由6降到5。證明過程我們使用的是平面圖的Euler公式，利用權(quán)轉(zhuǎn)移的方法進(jìn)行證明得出結(jié)果。
　　在第三章中，我們將平面圖的點(diǎn)染色研究推廣到1-平面圖的點(diǎn)染色研究，由正常的點(diǎn)染色問題研究推廣到對(duì)每個(gè)剖分的生成子圖中頂點(diǎn)的度數(shù)做限制的退化點(diǎn)染色研究。受X.Luo,M.Chen,

10、Wang。等人在參考文獻(xiàn)[17][18][19]中研究的啟發(fā),本文考慮的是不含3,4,5圈的1-平面圖的退化點(diǎn)染色，得到下面的結(jié)果：
　　定理2.不含3,4,5圈的1-平面圖是（1,1,1,1)-可染的；
　　定理2將1-平面圖的正常點(diǎn)染色推廣到不含某些結(jié)構(gòu)的1-平面圖的退化點(diǎn)染色，將每個(gè)色集的點(diǎn)導(dǎo)出子圖由正常染色的點(diǎn)獨(dú)立集放松到點(diǎn)導(dǎo)出子圖中頂點(diǎn)的度數(shù)均不大于1.色數(shù)由6降到4。
　　在第四章中，我們提出了一種新的非正

11、常點(diǎn)染色。在這種非正常點(diǎn)染色中,我們沒有對(duì)單色集的導(dǎo)出子圖中頂點(diǎn)的度數(shù)做限制，而是使得單色集的導(dǎo)出子圖中圍長至少為l或者不含長度為l的圈。
　　定義1:圖G=(V,E)為有限圖，給圖G的頂點(diǎn)集一個(gè)顏色分配，使得每個(gè)色類的導(dǎo)出子圖中圍長至少為l,滿足上述條件的染色稱為圖G的 l-圍長染色。圖G進(jìn)行l(wèi)-圍長染色所需要的最小的色數(shù)稱為圖G的l-圍長點(diǎn)色數(shù),記作χgl(G)。
　　定理3.G是一個(gè)圖，△≤4并且G≠K5,那么χgl(