论文部分内容阅读
如果一个图G的选择数等于它的色数,则称该图G是色可选择的.在2002年,Ohba给出如下猜想：每一个顶点个数小于等于2Х（G）＋1的图G是色可选择的.容易发现Ohba猜想成立的条件是当且仅当它对完全多部图成立,但是目前只是就某些特殊的完全多部图的图类证明了Ohba猜想的正确性.在本文我们证明图K6,3,2＊（k-6）,1＊4（k≥6）是色可选择的,从而对图K6,3,2＊（k-6）,1＊4（k≥6）和它们的所有完全k-部子图证明了Ohba猜想成立.