關于某些完全多部圖的色-可選擇性.pdf

1、如果一個圖G的選擇數(shù)等于它的色數(shù)，即Ch(G)=X(G)，則稱圖G是色一可選擇的。關于圖的色一可選擇性，2002年Ohba給出猜想：任意一個頂點的個數(shù)小于等于2X(G)+1的圖都是色一可選擇的。目前，針對一般的圖，對Ohba猜想的研究還沒有突出的進展。2005年Reed和Sudakovr用概率方法證明了Ohba猜想的一個較弱的形式：若|V(G)|≤5x(G)/3-4/3，則Ch(G)=X(G)。同時，他們指出Ohba猜想是漸進地正確的。

2、除此之外，人們只是對某些特殊的圖類驗證了Ohba猜想的正確性。由于每一個X-色圖都是一個完全X-部圖的子圖，容易發(fā)現(xiàn)Ohba猜想成立當且僅當其對完全多部圖成立。目前，對于至少有一部的頂點個數(shù)大于3的完全多部圖，已有的結果只是證明了恰好有一部的頂點個數(shù)為4，或5，或6的完全多部圖，即對圖Kt+2,3,2*(k-t-2),1*t(其中t≤4且k≥t+2)及其所有k-色子圖Ohba猜想成立。本文證明了 Ch(Kt+2,3,2*(k-t-2),