【摘要】：令G是一個有限簡單平面圖.用V(G)和E(G)分別表示圖G的頂點集和邊集,簡記為V和E.若存在一個映射π:V → {1,2,…,k}滿足對(?)xy∈E,都有π(x)≠ π(y),則稱π是圖G的一個正常k-點染色,并稱G是k-點可染的.圖G的點色數(shù)x(G)是使得G是k-點可染的最小正整數(shù)k的值.若G存在一種正常點染色,滿足不存在二色圈,則稱這種點染色是無圈的.也就是說,每個圈至少使用三種顏色.圖G的無圈點色數(shù),記作xa(G),是使得G有一個無圈k-點染色的最小正整數(shù)k的值.著名數(shù)學(xué)家Grunbaum教授于1973年最早提出圖的無圈點染色的概念,他證明了每個平面圖是無圈9-點可染的,同時猜想:每個平面圖是無圈5-點可染的,該猜想后被Borodin證明.給圖G中的每一個頂點v配置一個顏色集合L(v),記L={L(v)|v∈V},如果存在一種染色π,其中π(v)∈L(v),使得π是正常點染色,那么稱G是L-點可染的或稱G有一個L-點染色.若對所有的v ∈ V(G),配置任意的列表L,其中|L(v)|=k,使得G是L-點可染的,則稱G是k-點列表可染的.我們把使得G是k-點列表可染的最小正整數(shù)k的值稱為G的點列表色數(shù),記作xl(G).若存在一個無圈點染色π,使得對每個點v都有π(v)∈L(v),則稱G是無圈L-點可染的.同時染色π被稱作G的一個無圈L-點染色.類似地,當(dāng)|L(v)| = k且G是無圈L-點可染的,稱G是無圈k-點列表可染的.G的無圈點列表色數(shù)是使得G是無圈k-點列表可染的最小正整數(shù)k-的值,記作xal(G).2002 年,Borodin,Fon-Der Flaass,Kostochka,Raspaud 和 Sopena 首次提出并研究了平面圖的無圈點列表染色問題.他們證明了每個平面圖是無圈7-點列表可染的,并且提出了極具挑戰(zhàn)性的猜想:每個平面圖是無圈5-點列表可染的.而后,在2006年,Montassier,Raspaud和Wang進而提出了猜想:每個不包含4-圈的平面圖是無圈4-點列表可染的.這兩個猜想至今仍懸而未決.近年來,平面圖的無圈4-點列表染色問題引起了國內(nèi)外研究者的極大關(guān)注.本學(xué)位論文主要圍繞此問題展開研究.我們將給出平面圖為無圈4-點列表可染的新的充分條件.論文框架結(jié)構(gòu)及內(nèi)容如下:在第一章中,我們先給出本文將用到的基本概念,再簡述相關(guān)領(lǐng)域的研究現(xiàn)狀和本文的研究結(jié)果.在第二章,第三章和第四章中,我們均使用反證法,通過構(gòu)造極小反例,運用色延拓技巧以及經(jīng)典的權(quán)轉(zhuǎn)移方法,分別證明了以下三個結(jié)果:(1)每個不包含相交5--圈的平面圖是無圈4-點列表可染的.(2)每個既不包含4-圈,也不包含相交3-圈和相交5-圈的平面圖是無圈4-點列表可染的.(3)每個不包含4-,7-和9-圈的平面圖是無圈4-點列表可染的.
【圖文】：

圖３．１：引理３．７中兩種可能會發(fā)生的情況．逡逑
【學(xué)位授予單位】：浙江師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【相似文獻】

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

1 張軼;;“立方根”檢測題[J];中學(xué)生數(shù)理化(七年級數(shù)學(xué))(配合人教社教材);2017年03期

2 林炳生;;佩爾方程的最小正整數(shù)解[J];數(shù)學(xué)的實踐與認(rèn)識;2011年08期

3 高飛;論方程x~2-Dy~2=1的最小正整數(shù)解之求法[J];內(nèi)蒙古電大學(xué)刊;2003年06期

4 白椿;;歐拉定理解決同余問題的進一步探討[J];科技信息;2011年33期

5 ;問題10.2解答[J];初中生數(shù)學(xué)學(xué)習(xí);2000年02期

6 樸濟賢;;關(guān)于k=4.5~(n-1)[J];佳木斯教育學(xué)院學(xué)報;1987年03期

7 徐榮貴;;一個錯誤的解答[J];數(shù)學(xué)教學(xué)通訊;1995年02期

8 邊欣,李忠民;關(guān)于不定方程x~2-Dy~2=c的最小正整數(shù)解[J];工科數(shù)學(xué);2002年04期

9 樸濟賢;;關(guān)于十進制有限純小數(shù)轉(zhuǎn)換為七進制無限純循環(huán)小數(shù)的定理[J];佳木斯教育學(xué)院學(xué)報;1987年02期

10 趙東方;運用Mathematica4軟件包求解Pell方程的方法[J];華中師范大學(xué)學(xué)報(自然科學(xué)版);2003年03期

相關(guān)會議論文 前1條

1 王學(xué)平;;Fuzzy關(guān)系廣義分解的一種新算法[A];模糊集理論與應(yīng)用——98年中國模糊數(shù)學(xué)與模糊系統(tǒng)委員會第九屆年會論文選集[C];1998年

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

1 高毓平;圖的邊染色及一些有限制條件的染色[D];山東大學(xué);2016年

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

1 孫英才;平面圖的無圈點列表染色[D];浙江師范大學(xué);2018年

2 韓云娜;關(guān)于一類丟番圖方程整數(shù)解的討論與研究[D];西北大學(xué);2011年

3 李偉;涉及5冪次的判別子問題[D];南京大學(xué);2013年

4 王偉;3色Ramsey數(shù)R（C_m_1，C_m_2，，C_m_3）[D];大連理工大學(xué);2006年

5 許仁譽;圖的全染色與度之冪和[D];山東大學(xué);2013年

本文編號：2655275