關(guān)于某些完全多部圖的色-可選擇性.pdf

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

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