圖的列表點蔭度.pdf

1、圖G的點蔭度是G的頂點集V(G)的最小劃分數(shù)，使得每個點劃分集的導出子圖是一個森林.圖G的一個k-森林染色是指一個映射φ:V(G)→{1，2，…，k}，使得每一個點導出子圖G[Vi]是一個森林，其中Vi是顏色為i的頂點集.G的點蔭度是指G有一個k-森林染色的數(shù)k的最小值，用a(G)表示.
　　若G有一個森林染色π，使得對每個頂點v都有π(v)∈L(v)，那么就稱G是L-森林可染的.若對于任意列表|L(x)|≥k，G是L-森林可染的

2、，那么就稱G是k-列表森林可染的.G的列表點蔭度是指G是k-列表森林可染的數(shù)k的最小值，用al(G)表示.
　　點蔭度最早是由Chartrand，Kronk和Wall于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)

3、≤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-圈不相鄰的平面圖，則al(G)≤2.那么，對于環(huán)面圖而言，上述結(jié)果是否仍成立呢？
　　本學位論文主要研究了平面圖和環(huán)面圖的列表點蔭度

4、問題，共分三章.
　　在第一章中，我們介紹了基本概念和相關(guān)領(lǐng)域的研究現(xiàn)狀，并且呈現(xiàn)了本文的主要結(jié)果.
　　在第二章中，我們研究了環(huán)面圖的列表點蔭度，證明了下面三個結(jié)果:
　　(1)若G是3-圈與5-圈不相鄰的環(huán)面圖，則al(G)≤2.
　　(2)若G是4-圈與5-圈不相鄰的環(huán)面圖，則al(G)≤2.
　　(3)若G是3-圈與4-圈不相鄰的環(huán)面圖，則alG)≤2.
　　在第三章中，我們研究了平面圖的列表