某些特殊圖的點染色問題研究.pdf

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

2、g[5]提出猜想：不含4-圈和5-圈的平面圖是3-可染的。為了證明Steinberg猜想，學者把平面圖的正常點染色推廣到非正常點染色，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的點染色是對圖G的頂點集的一種剖分.如果圖G的頂點集V可以剖分成互不相交的k個部分，給每一部分染上同一種顏色并且使得每部分的生成子圖滿足某種要求。若剖分產(chǎn)生的各部分都是點獨立集，則為圖G的正常點染色，否則稱為圖G的非正常點染色。如果對每部分剖分的導出子圖中頂點的度數(shù)做限制,使得G[Vi]中所有頂點的度均不超過忒

4、,則稱圖G是(d1,d2,…,dk)-可染的[12]。圖的色數(shù)是指給一個圖染色所用的最少顏色數(shù)。如果存在映射Φ:V→(1,…,dk},滿足uv∈E時,Φ(u)=Φ(v),則稱Φ是G的一個k-染色。若G有一個k-染色，則稱G是k-可染的。
　　關于圖的正常點染色，主要有以下結(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-可染性。關于圖的對每個剖分中點的度數(shù)做限制的非正常點染色，主要有以下結(jié)果：
　?、湃魣DG為

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]);
　　基于目前對圖的點染色的研究，本人跟隨前面學者的腳步，繼續(xù)對圖的染

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

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

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

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