本文關(guān)鍵詞：某些特殊圖的點(diǎn)染色問題研究

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

【摘要】：圖論是現(xiàn)代數(shù)學(xué)的重要分支之一,圖的染色問題是圖論中的熱點(diǎn)也是難點(diǎn).圖的染色問題起源于著名的“四色定理”,即給平面上的任何一張地圖著色,使得有公共邊界的國(guó)家染上不同的顏色,至多使用四種顏色([1-3]).后來,有些學(xué)者將平面圖的染色問題擴(kuò)展到1-平面圖的染色研究.一個(gè)圖稱為是1-平面的當(dāng)且僅當(dāng)它可以畫在一個(gè)平面上,使得它的任何一條邊最多交叉另外一條邊.1984年,Bordin證明了1-平面圖是6-可染的.1976年,Steinberg提出猜想：不含4-圈和5-圈的平面圖是3-可染的.為了證明Steinberg猜想,學(xué)者把平面圖的正常點(diǎn)染色推廣到非正常點(diǎn)染色,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的點(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)的度均不超過di,則稱圖G是(d1,d2,…,dk)-可染的.圖G的k染色是指圖G能夠正常點(diǎn)染色所需要的色數(shù)至少為k.如果圖G有一個(gè)k染色,又稱圖G是k-可染的.關(guān)于圖的正常點(diǎn)染色,主要有以下結(jié)果：(1)[四色定理]平面圖是4-可染的；(2)1-平面圖是6-可染的([4])；(3) [Steinberg猜想[5]]不含4-圈和5-圈的平面圖是3-可染的；(4)若圖G為平面圖,且不含長(zhǎng)度為4,5,6,7的圈,則圖G是3-可染的([13])；(5)若圖G為平面圖,且不含長(zhǎng)度為4,5,6,8的圈,則圖G是3-可染的([14])；(6)若圖G為平面圖,且不含長(zhǎng)度為4,5,6,9的圈,則圖G是3-可染的([15])；(7)若圖G為平面圖,且不含長(zhǎng)度為4,5,7,8的圈,則圖G是3-可染的([16])；(8)若圖G為平面圖,且不含長(zhǎng)度為4,6,7,8的圈,則圖G是3-可染的([17])；(9)若圖G為平面圖,且不含長(zhǎng)度為4,6,8,9的圈,則圖G是3-可染的([18])；(10)若圖G為平面圖,且不含長(zhǎng)度為4,7,8,9的圈,則圖G是3-可染的([19])；此外,Bordin等人在([20-26])中也研究了平面圖的3-可染性.關(guān)于圖的對(duì)每個(gè)剖分中點(diǎn)的度數(shù)做限制的非正常點(diǎn)染色,主要有以下結(jié)果：(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])；基于目前對(duì)圖的點(diǎn)染色的研究,本人跟隨前面學(xué)者的腳步,繼續(xù)對(duì)圖的染色問題進(jìn)行研究.在第一章主要介紹了論文中所涉及的一些概念和術(shù)語符號(hào)以及本文的研究背景和已有的一些結(jié)果.在第二章中,我們?nèi)匀豢紤]傳統(tǒng)的正常點(diǎn)染色問題,但我們將平面圖的正常點(diǎn)染色研究推廣到1-平面圖的正常點(diǎn)染色研究Bordin證明了1-平面圖是6-可染的,本文考慮不含4-圈且5-點(diǎn)不與5-點(diǎn)相鄰的1-平面圖的點(diǎn)染色,得到下面的結(jié)果：定理1.如果圖G是1-平面圖,滿足：(1)圖G不包含4-圈;(2)圖G中5-點(diǎn)不與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)染色研究.受XLuo, M. Chen, 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.在第四章中,我們提出了一種新的非正常點(diǎn)染色.在這種非正常點(diǎn)染色中,我們沒有對(duì)單色集的導(dǎo)出子圖中頂點(diǎn)的度數(shù)做限制,而是使得單色集的導(dǎo)出子圖中不含長(zhǎng)度為l的圈.基于我們?cè)诘诙�、三章中�?duì)圖的染色問題的討論,不難發(fā)現(xiàn),很多圖的染色問題需要限制掉某些長(zhǎng)度的圈,所以我們提出的新問題對(duì)圖論中染色問題的研究具有一定的意義.定義：圖G=(V, E)為有限圖,給圖G的頂點(diǎn)一個(gè)恰當(dāng)?shù)念伾峙?使得每個(gè)色類的導(dǎo)出子圖不含長(zhǎng)為l的圈,滿足上述染色條件的最小的色數(shù)稱為圖G的最小無l圈點(diǎn)色數(shù),記作χct-f(G).本文主要考慮最大度較小的情況下,使得剖分中不含長(zhǎng)為3-圈和4-圈非正常點(diǎn)染色.得到如下結(jié)果：定理3.△≤4時(shí),若G≠K5,χc3-f(G)≤2.定理4.△≤4時(shí),χc4-f(G)=2.
【關(guān)鍵詞】：5-可染的 (1 1 1 1)-可染的 1-平面圖 4-圈
【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5
【目錄】：

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

【參考文獻(xiàn)】

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

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

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

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

，

本文編號(hào)：641769