本文關鍵詞：某些特殊圖的點染色問題研究

  更多相關文章： 5-可染的 (1 1 1 1)-可染的 1-平面圖 4-圈

【摘要】：圖論是現(xiàn)代數(shù)學的重要分支之一,圖的染色問題是圖論中的熱點也是難點.圖的染色問題起源于著名的“四色定理”,即給平面上的任何一張地圖著色,使得有公共邊界的國家染上不同的顏色,至多使用四種顏色([1-3]).后來,有些學者將平面圖的染色問題擴展到1-平面圖的染色研究.一個圖稱為是1-平面的當且僅當它可以畫在一個平面上,使得它的任何一條邊最多交叉另外一條邊.1984年,Bordin證明了1-平面圖是6-可染的.1976年,Steinberg提出猜想：不含4-圈和5-圈的平面圖是3-可染的.為了證明Steinberg猜想,學者把平面圖的正常點染色推廣到非正常點染色,Xu證明了不含4-圈和5-圈的平面圖是(1,1,0)-可染的；Hill證明了不含4-圈和6-圈的平面圖是(3,0,0)-可染的；Xu證明了不含4-圈和6-圈的平面圖是(1,1,0)-可染的；Wang證明了不含4-圈和6-圈的平面圖是(2,0,0)-可染的等等.2011年,Chang研究了Steinberg猜想并考慮了附近的染色.1986年L. Cowen提出了圖的缺陷染色.圖G的點染色是對圖G的頂點集的一種剖分.如果圖G的頂點集V可以剖分成互不相交的k個部分,給每一部分染上同一種顏色并且使得每部分的生成子圖滿足某種要求.若剖分產生的各部分都是點獨立集,則為圖G的正常點染色,否則稱為圖G的非正常點染色.如果對每部分剖分的導出子圖中頂點的度數(shù)做限制,使得G[Vi]中所有頂點的度均不超過di,則稱圖G是(d1,d2,…,dk)-可染的.圖G的k染色是指圖G能夠正常點染色所需要的色數(shù)至少為k.如果圖G有一個k染色,又稱圖G是k-可染的.關于圖的正常點染色,主要有以下結果：(1)[四色定理]平面圖是4-可染的；(2)1-平面圖是6-可染的([4])；(3) [Steinberg猜想[5]]不含4-圈和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為平面圖,且不含長度為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ù)做限制的非正常點染色,主要有以下結果：(1)若圖G為平面圖,且不含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])；(4)若圖G為平面圖,且不含4-圈和6-圈,則圖G是(2,0,0)-可染的([10])；基于目前對圖的點染色的研究,本人跟隨前面學者的腳步,繼續(xù)對圖的染色問題進行研究.在第一章主要介紹了論文中所涉及的一些概念和術語符號以及本文的研究背景和已有的一些結果.在第二章中,我們仍然考慮傳統(tǒng)的正常點染色問題,但我們將平面圖的正常點染色研究推廣到1-平面圖的正常點染色研究Bordin證明了1-平面圖是6-可染的,本文考慮不含4-圈且5-點不與5-點相鄰的1-平面圖的點染色,得到下面的結果：定理1.如果圖G是1-平面圖,滿足：(1)圖G不包含4-圈;(2)圖G中5-點不與5-點相鄰.那么圖G是5-可染的.定理1是在1-平面圖的正常點染色中,限制掉圖中的4-圈,滿足5-點不與5-點相鄰,將1-平面圖的正常點染色色數(shù)由6降到5.證明過程我們使用的是平面圖的Euler公式,利用權轉移的方法進行證明得出結果.在第三章中,我們將平面圖的點染色研究推廣到1-平面圖的點染色研究,由正常的點染色問題研究推廣到對每個剖分的生成子圖中頂點的度數(shù)做限制的退化點染色研究.受XLuo, M. Chen, Wang等人在參考文獻[17][18][19]中研究的啟發(fā),本文考慮的是不含3,4,5圈的1-平面圖的退化點染色.得到下面的結果：定理2.不含3,4,5圈的1-平面圖是(1,1,1,1)-可染的；定理2將1-平面圖的正常點染色推廣到不含某些結構的1-平面圖的退化點染色,將每個色集的點導出子圖由正常染色的點獨立集放松到點導出子圖中頂點的度數(shù)均不大于1.色數(shù)由6降到4.在第四章中,我們提出了一種新的非正常點染色.在這種非正常點染色中,我們沒有對單色集的導出子圖中頂點的度數(shù)做限制,而是使得單色集的導出子圖中不含長度為l的圈.基于我們在第二、三章中對圖的染色問題的討論,不難發(fā)現(xiàn),很多圖的染色問題需要限制掉某些長度的圈,所以我們提出的新問題對圖論中染色問題的研究具有一定的意義.定義：圖G=(V, E)為有限圖,給圖G的頂點一個恰當?shù)念伾峙?使得每個色類的導出子圖不含長為l的圈,滿足上述染色條件的最小的色數(shù)稱為圖G的最小無l圈點色數(shù),記作χct-f(G).本文主要考慮最大度較小的情況下,使得剖分中不含長為3-圈和4-圈非正常點染色.得到如下結果：定理3.△≤4時,若G≠K5,χc3-f(G)≤2.定理4.△≤4時,χc4-f(G)=2.
【關鍵詞】：5-可染的 (1 1 1 1)-可染的 1-平面圖 4-圈
【學位授予單位】：山東師范大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 中文摘要6-10
• 英文摘要10-15
• 第一章 引言15-22
• 1.1 基本概念15-17
• 1.2 染色問題的研究現(xiàn)狀17-20
• 1.3 本文的主要結果20-22
• 第二章 某些不含4圈的1-平面圖是5-可染的22-33
• 2.1 預備知識22-23
• 2.2 結構性質23
• 2.3 定理1的證明23-33
• 第三章 不含3,4,5圈的1-平面圖是(1,1,1,1)-可染的33-44
• 3.1 預備知識33-34
• 3.2 結構性質34-35
• 3.3 定理2的證明35-44
• 第四章 某些特殊圖的非正常點染色44-52
• 4.1 預備知識44
• 4.2 定理3和4的證明44-52
• 參考文獻52-56
• 攻讀學位期間發(fā)表的學術論文56-57
• 致謝57

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前3條

1 徐靈姬;王應前;;既不含4-圈又不含6-圈的平面圖的非正常染色[J];中國科學:數(shù)學;2013年01期

2 張欣;劉桂真;吳建良;;不含3-圈的1-平面圖的邊染色[J];山東大學學報(理學版);2010年06期

3 ;A 3-color Theorem on Plane Graphs without 5-circuits[J];Acta Mathematica Sinica(English Series);2007年06期

，

本文編號：641769