本文關鍵詞：環(huán)面圖的列表染色

  更多相關文章： 環(huán)面圖 正常列表染色 非正常列表染色 圈 權轉移

【摘要】：本文研究的圖是有限,簡單,無向圖.設G是一個環(huán)面圖,是指圖G可以嵌入到環(huán)面上,即在環(huán)面上無交叉的邊.G的正常列表染色是指,G的一個頂點色表配置L是一個色集簇,L={l(V)|(?)∈V,L(v)(?)N}其中L(v)叫做v的可用色表,若映射φ：V→N滿足：(1)φ(x)∈L(u),(?)∈V；(2)uv∈E(?)φ(u)≠φ(v)則稱φ是G的一個L-染色.若G存在一個L-染色,則稱G是L-可染的.若對每一個滿足|L(v)|≥κ的色表配置L, G都是L-可染的,則稱G是κ-可選的.令d是一個非負整數(shù).G是(L,d)*-可染的,是指存在某個染色φ,使得φ(u)∈L(v)且滿足G的每個頂點至多與其d個鄰點染相同顏色.G的非正常列表染色,即G是(κ,d)*-可選的,是指(?)v∈V(G)分配一個色表L,|L(u)|≥k,且都存在一個(L,d)*-染色.易知,正常列表染色是非正常列表染色的特例,非正常列表染色是正常列表染色的推廣圖G的一個正常染色φ,若能滿足G中的任意兩個色的點集所導出的子圖是一個星森林,則稱正常染色φ是G的一個星染色.若給定圖G的一個頂點色表配置L,且存在一個星染色φ使得κ(v)∈L(v),則稱G是L-星-可選的.若對每一個滿足|L(v)|)≥κ的色表配置L,G都是L-星-可染的,則稱G是κ-星-可選的.在平面圖上,正常列表染色和非正常列表染色已有不少猜想和問題已經(jīng)被許多研究者所解決和證明,于是研究者開始進一步思考這些結論是否仍然適用于環(huán)面圖上,后人展開了相關的研究工作并取得了一系列的成果.本論文分為四章,主要圍繞環(huán)面圖的列表染色展開研究,所得到的結論改進了現(xiàn)有的一些結果.第一章介紹了本論文所涉及的有關定義,并對正常列表染色和非正常列表染色的研究現(xiàn)狀做了一個綜述.第二章介紹了不含4-圈和i-圈(i∈{5,7,8})的環(huán)面圖是(3,1)*-可選的.第三章介紹了不含4,i,j-圈((i,j)∈{(5,7),(6,8)})且三角形距離至少為3的環(huán)面圖是3-可選的.第四章介紹了最大度不大于3的環(huán)面圖是6-星-可選的.
【關鍵詞】：環(huán)面圖 正常列表染色 非正常列表染色 圈 權轉移
【學位授予單位】：浙江師范大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要3-5
• ABSTRACT5-9
• 1 緒論9-16
• 1.1 基本概念9-11
• 1.2 環(huán)面列表染色的研究概況11-14
• 1.3 本文的主要結果14-16
• 2 關于環(huán)面圖的非正常列表染色可染的結果16-29
• 2.1 關于(3,1)~*-可選的可約構型16-18
• 2.2 定理2.1的證明18-21
• 2.3 定2.2的證明21-24
• 2.4 定理2.3的證明24-29
• 3 關于環(huán)面圖的正常列表染色可染的結果29-34
• 3.1 定理3.1的證明29-31
• 3.2 定理3.2的證明31-34
• 4 關于環(huán)面圖的星列表染色的結果34-44
• 4.1 關于最大度△≤3的環(huán)面圖的可約構型34-42
• 4.2 定理4的證明42-44
• 參考文獻44-47
• 在學期間的研究成果及發(fā)表的論文47-48
• 致謝48-51
• 附件51

【相似文獻】

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

1 鄒健;胡崗;;從三維環(huán)面到混沌[J];北京師范大學學報(自然科學版);1987年02期

2 黃化宇;環(huán)面的一種特殊切面[J];贛南師范學院學報;1990年S2期

3 李炳仁,林青;C~*-代數(shù)映象環(huán)面的注記[J];科學通報;1992年19期

4 余澍祥;環(huán)面上動力系統(tǒng)的某些性質(英文)[J];數(shù)學研究與評論;1992年02期

5 符五久,何娟美;準周期驅動圓映射的環(huán)面分岔機制及標度關系[J];南昌大學學報(理科版);2005年02期

6 尚新春,程昌鈞;環(huán)面薄膜的膨脹失穩(wěn)[J];應用數(shù)學和力學;1991年06期

7 任軍,章輝煌,林尊琪;掠入射光柵譜儀中的超環(huán)面鏡對線狀X光光源診斷的影響[J];量子電子學;1992年01期

8 陶志雄;;環(huán)面鏈環(huán)的多項式[J];浙江科技學院學報;2013年06期

9 鄧小國;周泗忠;熊仁生;郭治理;;超環(huán)面聚焦鏡壓彎裝置的優(yōu)化設計[J];光子學報;2006年05期

10 鮑園園;雷逢春;;環(huán)面鏈環(huán)的辮子數(shù)(英文)[J];黑龍江大學自然科學學報;2008年02期

中國重要會議論文全文數(shù)據(jù)庫 前2條

1 洪玫;姚立綱;;基于數(shù)值方法的內超環(huán)面行星齒輪齒廓離散建模[A];第十五屆中國科協(xié)年會第27分會場：現(xiàn)代圖學推動數(shù)字設計與制造論壇論文集[C];2013年

2 謝建華;丁旺才;;多自由度碰撞振動系統(tǒng)環(huán)面分岔與混沌研究[A];第七屆全國非線性動力學學術會議和第九屆全國非線性振動學術會議論文集[C];2004年

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 張建路;KAM環(huán)面的漸近軌道[D];南京大學;2014年

中國碩士學位論文全文數(shù)據(jù)庫 前9條

1 景昱波;環(huán)面圖的列表染色[D];浙江師范大學;2015年

2 曹瀧;叉排圓管非對稱間斷環(huán)面槽換熱器翅片傳熱特性的數(shù)值研究[D];蘭州交通大學;2014年

3 鄧潤林;牽引式全環(huán)面IVT設計方法的初步研究[D];華中科技大學;2005年

4 董操;二維環(huán)面的匹配排除[D];山西大學;2010年

5 趙雯洲;K_7在環(huán)面上的嵌入[D];華東師范大學;2012年

6 秦玉鳳;環(huán)面紐結T_(3,2n)、T_(4,2n)在廣義方格圖中的嵌入問題和完全3-部圖K_(2,5,n)的交叉數(shù)[D];東北師范大學;2014年

7 黃探霄;CP~n中具有循環(huán)調和序列的平坦極小環(huán)面[D];南昌大學;2010年

8 崔懷愈;超環(huán)面鏡聚焦46.9nm軟X射線激光燒蝕固體靶的實驗研究[D];哈爾濱工業(yè)大學;2013年

9 孫媛媛;環(huán)面上的頂點代數(shù)層結構的實現(xiàn)[D];河南大學;2009年

，

本文編號：602417