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

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

【摘要】：本文研究的圖是有限,簡單,無向圖.設(shè)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是一個非負(fù)整數(shù).G是(L,d)*-可染的,是指存在某個染色φ,使得φ(u)∈L(v)且滿足G的每個頂點至多與其d個鄰點染相同顏色.G的非正常列表染色,即G是(κ,d)*-可選的,是指(?)v∈V(G)分配一個色表L,|L(u)|≥k,且都存在一個(L,d)*-染色.易知,正常列表染色是非正常列表染色的特例,非正常列表染色是正常列表染色的推廣圖G的一個正常染色φ,若能滿足G中的任意兩個色的點集所導(dǎo)出的子圖是一個星森林,則稱正常染色φ是G的一個星染色.若給定圖G的一個頂點色表配置L,且存在一個星染色φ使得κ(v)∈L(v),則稱G是L-星-可選的.若對每一個滿足|L(v)|)≥κ的色表配置L,G都是L-星-可染的,則稱G是κ-星-可選的.在平面圖上,正常列表染色和非正常列表染色已有不少猜想和問題已經(jīng)被許多研究者所解決和證明,于是研究者開始進(jìn)一步思考這些結(jié)論是否仍然適用于環(huán)面圖上,后人展開了相關(guān)的研究工作并取得了一系列的成果.本論文分為四章,主要圍繞環(huán)面圖的列表染色展開研究,所得到的結(jié)論改進(jìn)了現(xiàn)有的一些結(jié)果.第一章介紹了本論文所涉及的有關(guā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-星-可選的.
【關(guān)鍵詞】：環(huán)面圖 正常列表染色 非正常列表染色 圈 權(quán)轉(zhuǎn)移
【學(xué)位授予單位】：浙江師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：602417