關(guān)于圖的可選擇性與唯一列表可染圖研究.pdf

1、本文研究列表染色的若干問題，包括圖的色-可選擇性和Ohba猜想、某些平面圖的(k,l)-可選擇性和(k,l)-邊-可選擇性，以及圖(尤其是完全多部圖)的唯一列表可染性. 如果圖G滿足Ch(G)=χ(G)，則稱G是色-可選擇的.關(guān)于圖的色-可選擇性，2002年Ohba[71]給出猜想：如果圖G滿足|V(G)|≤2χ(G)+1，則G是色-可選擇的.容易發(fā)現(xiàn)Ohba猜想成立當(dāng)且僅當(dāng)其對完全多部圖成立，但是對完全多部圖Ohba猜想被驗證

2、的情況只有圖K3*2,2*(k-3),1、K3,2*(k-1)和Kt+3，2*(k-t-1)，1*t·本文證明：完全多部圖Kt+2,3,2*(k-t-2),1*t(t=2，3，4；k≥t+2)是色-可選擇圖.因此得到，對圖Kt+2，3，2*(k-t-2)，1*t(t=1，2，3，4；k≥t+2)及其所有k-色子圖Ohba猜想成立.對獨立數(shù)最大為3的圖，2004年Ohba[72]證明了Ohba猜想的一個較弱的形式：如果圖G滿足|V(G)|

3、≤2χ(G)，且G的獨立數(shù)最大為3，則G是色-可選擇的.在此我們證明：若r≤t+1且k≥r+t，則Ch(K3*r,2*(k-r-t),1*t)=χ(K3*r,2*(k-r-t),1*t)=k.此結(jié)果表明：在如上Ohba的論斷中，條件|V(G)|≤2χ(G)可以換成|V(G)|≤2χ(G)+1.即對每個獨立數(shù)最大為3的圖及其所有χ(G)-色子圖Ohba猜想成立. 圖的(k,l)-可選擇性問題是圖的k-可選擇性問題的推廣.關(guān)于圖的(

4、k,l)-可選擇性，1979年Erdos等人[26]提出了如下猜想：對任意整數(shù)m≥1，每一個(k,l)-可選擇的圖G也是(km，lm)-可選擇的.1996年Tuza和Voigt[94]證明了這個猜想在k=2和l=1的情形是正確的，但是對任意的(k，l)驗證這個猜想的工作還相差甚遠(yuǎn).本文證明：對任意整數(shù)m≥1，每一個沒有t-圈(t=3，4，5或6)的平面圖是(4m，m)-可選擇的.這一結(jié)果推廣了分別由Lam等人[65]、由Wang和Lih

5、[106]、由Fijavz等人[28]給出的如上圖都是4-可選擇的結(jié)果.另一方面，我們還證明：如果一個平面圖G不包含t-圈(t=3，4，5或6)且△(G)≠4，則對任意整數(shù)m≥1，G是(sm，m)-邊-可選擇的，這里當(dāng)t∈{3，4，5}，或t=6但△(G)≠5時，s=△(G)+1；當(dāng)t=6且△(G)=5時，s=7.除了△(G)=4以及t=6且△(G)=5的情況之外，該結(jié)果推廣了分別由Wang和Lih[105，106]、Zhang和Wu[

6、114]、王維凡[117]給出的不包含t-圈(t=3，4，5或6)的平面圖都是(△(G)+1)-邊-可選擇的結(jié)果.此外，作為我們主要結(jié)果的推論得到：每一個沒有4-圈的平面圖G都是(△(G)十1)-邊-可選擇的.該結(jié)果也改進(jìn)了Zhang和Wu給出的結(jié)果：如果圖G是沒有4-圈的平面圖，則G是s-邊-可選擇的，這里當(dāng)△(G)≠5時，s=△(G)+1；當(dāng)△(G)=5時，s=7. 如果圖G存在一個k-列表安排L，使得G有唯一的一個L-染色

7、，則稱G是唯一k-列表可染的，簡稱G是UkLC圖.1999年Mahdian和Mahmoodian[67]特征化了U2LC圖.2001年Ghebleh和Mahmoodian[32]深入地研究了完全多部圖的唯一列表可染性，尤其是唯一3-列表可染性，除去9個完全多部圖不能確定之外，他們特征化了U3LC完全多部圖.與此同時，針對這9個被剔除的圖，他們提出了如下開放問題：查證圖K2,2,r，r=4，5，…，8，K2,3,4，K1*4,4，K1*4