本文主要研究了兩種特殊圖類的染色問題:不含三角形的平面圖的列表染色,交叉數(shù)為1的圖的在線列表染色.不含三角形的平面圖的染色問題吸引了很多學(xué)者的注意.Grotzsch的一個(gè)經(jīng)典結(jié)果即每個(gè)不含三角形的平面圖是3-可染的.Voigt構(gòu)造了一個(gè)不是3-可選的不含三角形的平面圖.Kratochvil和Tuza觀察到每一個(gè)不含三角形的平面圖是4-可選的.我們討論如下的問題:G是一個(gè)不含三角形的平面圖,X是G的頂點(diǎn)集的一個(gè)子集.L是G的一個(gè)列表配置,X中頂點(diǎn)的表長是3,其他頂點(diǎn)的表長是4.X滿足什么條件時(shí),G一定是L-可選的.由Kratochvil和Tuza的結(jié)果可知,X是空集時(shí),則G一定是L-可染的.由Voigt的結(jié)果可知,對于某些G,存在X,G不是L-可染的.在本文我們證明了一個(gè)結(jié)果:如果X是G中的一個(gè)獨(dú)立集,那么G是L-可染的.我們進(jìn)一步猜想:如果G[X]是一個(gè)二部圖,那么G是L-可染的.在線列表染色概念是由U.Schauz和X.Zhu于2009年分別提出.在線列表染色概念被提出以來,不少學(xué)者研究了各種圖類的在線列表染色.U.Schauz證明了平面圖是在線5-可選的,M.Han和X.Zhu證明了局部平面圖是在線5-可選的,M.Han和X.Zhu證明了每個(gè)局部平面圖是2-缺陷在線4-可選的,等相關(guān)性成果.我們證明了交叉數(shù)為1的圖是在線5-可選的.在研究過程中我們證明了如下結(jié)果:令G是一個(gè)交叉數(shù)至多為1的圖,T=[t1t2t3]為G中的一個(gè)三角形,f是V(G)到N的一個(gè)映射.如果V(T)中的點(diǎn)v滿足f(v)= 1,V(G)-VT)中的點(diǎn)v滿足f(v)=5,那么G-E(T)是在線f-可選的.
【學(xué)位單位】：浙江師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類】：O157.5
【部分圖文】：

圖２．１：?ｆ．Ｚ／）沒有壞４－圈??
【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李曉軍;曹世鵬;;兩類樹的獨(dú)立集多項(xiàng)式的單峰性[J];高等數(shù)學(xué)研究;2010年04期

2 謝力同;論簡單圖所含k階i爪獨(dú)立集個(gè)數(shù)的可重構(gòu)性[J];數(shù)學(xué)物理學(xué)報(bào);2001年02期

3 張蓮珠;兩類四角系統(tǒng)的匹配數(shù)與點(diǎn)獨(dú)立集數(shù)[J];數(shù)學(xué)研究;1999年03期

4 李國君，劉振宏;3－連通正則無爪圖的Hamilton圈[J];數(shù)學(xué)進(jìn)展;1996年01期

5 林育青;關(guān)于簡單圖的獨(dú)立集多項(xiàng)式[J];東北重型機(jī)械學(xué)院學(xué)報(bào);1997年02期

6 高太平,李素珍;關(guān)于3-連通非Hamilton無爪圖的一個(gè)注記[J];山西大學(xué)學(xué)報(bào)(自然科學(xué)版);1997年01期

7 程為麟;張忠輔;;關(guān)于Ramsey數(shù)的若干問題[J];甘肅教育學(xué)院學(xué)報(bào)(自然科學(xué)版);1988年01期

8 陳莉;周賀;何海霞;孫宏慧;陸星家;;基于最大權(quán)重獨(dú)立集的行人檢測研究[J];寧波工程學(xué)院學(xué)報(bào);2013年03期

9 梁作松;管梅;單而芳;;塊圖中的團(tuán)橫貫集和團(tuán)獨(dú)立集[J];通化師范學(xué)院學(xué)報(bào);2010年04期

10 艾爾肯·吾買爾;關(guān)于幾類Menger型圖[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);1995年04期

相關(guān)博士學(xué)位論文 前10條

1 張海良;關(guān)于圖的兩類多項(xiàng)式及相關(guān)指數(shù)的研究[D];華東師范大學(xué);2013年

2 曹月芬;多角鏈關(guān)于拓?fù)渲笜?biāo)的一些極值問題[D];廈門大學(xué);2008年

3 宋文兔;網(wǎng)絡(luò)分解在網(wǎng)絡(luò)編碼中的應(yīng)用[D];北京大學(xué);2012年

4 王世英;圖的匹配的若干結(jié)構(gòu)性問題[D];鄭州大學(xué);2000年

5 許成鑫;LDPC碼度分布特性及擴(kuò)展性應(yīng)用研究[D];北京郵電大學(xué);2011年

6 汪定國;正則圖的獨(dú)立集與團(tuán)橫貫[D];上海大學(xué);2013年

7 章舜哲;圖的哈密爾頓連通性及支撐樹特征研究[D];華中師范大學(xué);2015年

8 張一煒;源于幾類信息科學(xué)問題的極值組合構(gòu)型[D];浙江大學(xué);2016年

9 梁作松;圖的團(tuán)橫貫與團(tuán)染色[D];上海大學(xué);2013年

10 楊帆;群連通、圈覆蓋及相關(guān)問題的研究[D];華中師范大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 李晨瑩;圈圖在張量積下的獨(dú)立集結(jié)構(gòu)[D];浙江師范大學(xué);2018年

2 胡建章;特殊圖類的列表染色和在線列表染色[D];浙江師范大學(xué);2018年

3 王明昕;蜂窩網(wǎng)絡(luò)中密集D2D通信的資源分配方法研究[D];北京郵電大學(xué);2018年

4 胡幸威;動(dòng)力系統(tǒng)中有限IP-獨(dú)立集與其相關(guān)問題的研究[D];中國科學(xué)技術(shù)大學(xué);2017年

5 王華平;點(diǎn)獨(dú)立集度和的幾個(gè)結(jié)果[D];江西師范大學(xué);2002年

6 向慧芬;模糊獨(dú)立集系統(tǒng)及模糊擬陣的結(jié)構(gòu)研究[D];重慶大學(xué);2004年

7 鄒玲平;格子系統(tǒng)的獨(dú)立集的計(jì)數(shù)[D];廈門大學(xué);2007年

8 王吉松;基于最大權(quán)重獨(dú)立集的特征選擇方法研究[D];東北師范大學(xué);2013年

9 紀(jì)乃丹;圖的獨(dú)立集多項(xiàng)式和Clar覆蓋多項(xiàng)式的轉(zhuǎn)移矩陣計(jì)算[D];蘭州大學(xué);2006年

10 李樹花;關(guān)于κ-匹配和κ-獨(dú)立集的極值多聯(lián)苯鏈及一些和圖的點(diǎn)PI指標(biāo)[D];新疆師范大學(xué);2010年

本文編號(hào)：2860283