论文部分内容阅读
如果图G满足xl(G)=x(G),则称图G是色-可选择图。色-可选择图的充分条件已经有了大量的研究。2012年,Noel,Reed和Wu证明了Ohba猜想:如果图G满足|V(G)|≤2x(G)+1,则图G是色-可选择图.通过大量的研究已经得到:图K(2*k)是色-可选择的;当k≥3时,图K(3*1,2*(k-1))和图K(3*2,2*(k-2))是色-可选择的;当k是奇数时,图K(4*1,2*(k-1))是色-可选择的。但是,当k是偶数时,图K(4*1,2*(k-1))不是色-可选择图。另外,完全k部图K(3*k),图K(4*k),图K(5*1,2*(k-1))等都不是色-可选择图。 寻找色-可选择图时只需考虑完全多部图,但这类图有很多,如果先研究完全多部图是色-可选择图的必要条件,则这样可以缩小色-可选择图的的搜索范围,对以后研究色-可选择图具有非常重要的意义。 本文我们得到了色-可选择图的5个必要条件,全文共分为三个部分。 第一部分:阐述了与本论文研究问题相关的色-可选择图的背景,阐述本文的主要结论。 第二部分:给出两种简单完全多部图(二部图和图K(1*(k-2),m*1,n*1))是色-可选择图的必要条件。 第三部分:给出一般完全多部图K(n1,n2,…,nk)是色-可选择图的必要条件和两种特殊完全多部图K(3*t,2*(k-t)),K(4*l,3*r,2*t)是色-可选择图的必要条件。