论文部分内容阅读
图的染色是经典的图论问题,并且有着丰富的理论结果和广泛的实际应用。近年来大量的研究结果涌现在图的限制染色领域。图的限制染色是图的通常染色的一般化,列表染色就是其中的一种。近十年来,列表染色问题成为世界范围内众多图论学者的研究热点之一。本文研究列表染色中关于图的色.可选择性问题。如果图G满足Ch(G)=x(G),则称G是色.可选择的。关于图的色.可选择性,2002年()hba给出猜想:如果图G满足|V(G)|≤2x(G)+1,则G是色-可选择的。
容易发现Ohba猜想成立当且仅当其对完全多部图成立,但是对完全多部图Ohba猜想被验证的情况只有图K3,2*(k≥1)、Kt+3,2*(k-t-1),1*t(k≥
t+1)和Kt+2,3,2*(k-t-2),1*t(t=1,2,3,4;k≥t+2)。本文证明:完全多部图Kt+2,3,2*(k-t-2),1*t(t为偶数且t≥6;k≥t+2)是色.可选择图。因此得到,对图Kt+2,3,2*(k-t-2),1*t(t为偶数且t≥6;k≥t+2)及其所有k-色子图Ohba猜想成立。
本文一共分五章:第一章为绪论,主要介绍图论的发展史和本文研究的目的及意义;第二章为预备知识,介绍了图的一些基本知识和基本概念;第三章介绍了关于Ohba猜想的研究现状及已有结果;第四章证明了一类完全多部图的选择数,对其验证了Ohba猜想的正确性;
第五章为结论,总结了本论文的主要研究内容和结果。