一类完全多部图的色可选择性

如果一个图G的选择数等于它的色数,则称该图G是色可选择的．在2002年, Ohba给出如下猜想:每一个顶点个数小于等于2X(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猜想成立．

Chromatic Choosability of a Class of Complete Multipartite Graphs

A graph $G$ is called to be chromatic choosable if its choice number is equal to its chromatic number. In 2002, Ohba conjectured that every graph $G$ with $2\chi(G)+1$ or fewer vertices is chromatic choosable. It is easy to see that Ohba's conjecture is true if and only if it is true for complete multipartite graphs. But at present only for some special cases of complete multipartite graphs, Ohba's conjecture have been verified. In this paper we show that graphs $K_{6,3,2*(k-6),1*4}$ ($k\geq6$) is chromatic choosable and hence Ohba's conjecture is true for the graphs $K_{6,3,2*(k-6),1*4}$ and all complete $k$-partite subgraphs of them.