本文關(guān)鍵詞：圖的列表點蔭度

  更多相關(guān)文章： 列表點蔭度 點蔭度 森林染色 環(huán)面圖

【摘要】：圖G的點蔭度是G的頂點集V(G)的最小劃分?jǐn)?shù),使得每個點劃分集的導(dǎo)出子圖是一個森林.圖G的一個k-森林染色是指一個映射Φ：V(G)→{1,2…,k},使得每一個點導(dǎo)出子圖G[K]是一個森林,其中Vi是顏色為i的頂點集.G的點蔭度是指G有一個k-森林染色的數(shù)k的最小值,用a(G)表示.若G有一個森林染色π,使得對每個頂點v都有π(w) ∈ L(v),那么就稱G是L-森林可染的.若對于任意列表|L(x)|≥k,G是L-森林可染的,那么就稱G是k-列表森林可染的.G的列表點蔭度是指G是k-列表森林可染的數(shù)k的最小值,用a_l(G)表示.點蔭度最早是由Chartrand, Kronk和Wa_ll于1968年提出的.同時,他們證明了對任何圖G,有a(G)≤[Δ+1/2]；且若G是平面圖,則a(G)≤3.后來,Raspaud和Wang(2008), Huang, Shiu和Wang(2012)證明了：若G是不含k-圈,k∈{3,4,5,6,7},的平面圖,則a(G)≤2.2012年,Chen, Raspaud和Wang解決了Raspaud和Wang(2008)提出的猜想：若G是不含相交三角形的平面圖,則a(G)≤2.那么,若G是不含相交k-圈的平面圖,k∈{4,5,6,7},是否有a(G)≤2呢?Borodin和Ivanova證明了：若G是3-圈與4-圈不相鄰的平面圖,則a_l(G)≤2.那么,對于環(huán)面圖而言,上述結(jié)果是否仍成立呢?本學(xué)位論文主要研究了平面圖和環(huán)面圖的列表點蔭度問題,共分三章.在第一章中,我們介紹了基本概念和相關(guān)領(lǐng)域的研究現(xiàn)狀,并且呈現(xiàn)了本文的主要結(jié)果.在第二章中,我們研究了環(huán)面圖的列表點蔭度,證明了下面三個結(jié)果：(1)若G是3-圈與5-圈不相鄰的環(huán)面圖,則a_l(G)≤2.(2)若G是4-圈與5-圈不相鄰的環(huán)面圖,則a_l(G)≤2.(3)若G是3-圈與4-圈不相鄰的環(huán)面圖,則a_l(G)≤2.在第三章中,我們研究了平面圖的列表點蔭度,證明了：若G是不含相交5-圈的平面圖,則a_l(G)≤2.
【關(guān)鍵詞】：列表點蔭度 點蔭度 森林染色 環(huán)面圖
【學(xué)位授予單位】：浙江師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要3-4
• Abstract4-8
• 第一章 緒論8-14
• 1.1 基本概念8-9
• 1.2 點蔭度與列表點蔭度的研究概況9-13
• 1.3 本文主要結(jié)果13-14
• 第二章 環(huán)面圖的列表點蔭度14-50
• 2.1 一些記號14
• 2.2 3-圈與5-圈不相鄰的環(huán)面圖的列表點蔭度14-21
• 2.3 3-圈與4-圈不相鄰的環(huán)面圖的列表點蔭度21-33
• 2.4 4-圈與5-圈不相鄰的環(huán)面圖的列表點蔭度33-50
• 2.4.1 結(jié)構(gòu)引理34-44
• 2.4.2 主要結(jié)論及證明44-50
• 第三章 平面圖的列表點蔭度50-60
• 3.1 結(jié)構(gòu)性質(zhì)50-52
• 3.2 定理3.1的證明52-60
• 參考文獻60-62
• 攻讀學(xué)位期間取得的研究成果62-64
• 致謝64-66

【相似文獻】

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

1 吳建良;Halin圖的一些路分解[J];山東礦業(yè)學(xué)院學(xué)報;1998年01期

2 楊愛民;線圖的蔭度[J];山西大學(xué)學(xué)報(自然科學(xué)版);1998年01期

3 魏二玲,劉彥佩,楊愛民,康利;乘積圖的蔭度[J];北方交通大學(xué)學(xué)報;2000年02期

4 薛妮妮;嚴(yán)志丹;;關(guān)于曲面的列表點蔭度定義與探討[J];塔里木大學(xué)學(xué)報;2010年01期

5 王雪梅;李會序;;某些不含5-圈的圖的線性2-蔭度[J];科技信息;2011年29期

6 張忠輔;王建方;;蔭度與團覆蓋數(shù)的關(guān)系[J];蘭州鐵道學(xué)院學(xué)報;1991年01期

7 張忠輔;王建方;;關(guān)于圖的點蔭度[J];應(yīng)用數(shù)學(xué);1991年02期

8 張建州;;圖的點星蔭度[J];電子科技大學(xué)學(xué)報;1992年01期

9 熊黎明,文莉莉;圖的點線蔭度(英文)[J];江西師范大學(xué)學(xué)報(自然科學(xué)版);1994年02期

10 黃荷姣,魏暹蓀,張江濤;有限圖的邊蔭度分解[J];陜西師范大學(xué)學(xué)報(自然科學(xué)版);1998年04期

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

1 左連翠;圖的點蔭度和點線性蔭度[D];山東大學(xué);2005年

2 楊愛峰;圖的廣義著色[D];鄭州大學(xué);2004年

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

1 金政國;平方圖的點蔭度[D];北京交通大學(xué);2010年

2 姚梅;圈限制條件下平面圖的線性2-蔭度[D];河北工業(yè)大學(xué);2015年

3 趙宗正;短圈不相交的平面圖的線性2-蔭度[D];河北工業(yè)大學(xué);2015年

4 郭志偉;圖的強平衡頂點蔭度若干問題研究[D];青海師范大學(xué);2016年

5 黃莉;圖的列表點蔭度[D];浙江師范大學(xué);2016年

6 薛妮妮;圖的列表點蔭度[D];新疆大學(xué);2008年

7 石淼;k-退化圖的M圖的點蔭度[D];北京交通大學(xué);2010年

8 王苒群;幾類圖的線性k-蔭度[D];天津師范大學(xué);2013年

9 馬剛;平方圖的點蔭度[D];山東大學(xué);2007年

10 陶金穎;不含弦5-圈和弦6-圈的平面圖的線性2-蔭度[D];河北工業(yè)大學(xué);2014年

，

本文編號：981517