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

Chromatic Choosability of a Class of Complete Multipartite Graphs

中文关键词:  列表染色  完全多部图  色可选择图  Ohba猜想.

英文关键词:list coloring  complete multipartite graph  chromatic choosable graph  Ohba's conjecture.

中文摘要:

      如果一个图$G$的选择数等于它的色数,则称该图$G$是色可选择的. 在2002年, Ohba 给出如下猜想:每一个顶点个数小于等于$2\chi(G)+1$的图$G$是色可选择的.容易发现Ohba猜想成立的条件是当且仅当它对完全多部图成立,但是目前只是就某些特殊的完全多部图的图类证明了Ohba 猜想的正确性.在本文我们证明图$K_{6,3,2*(k-6),1*4}$($k\geq6$)是色可选择的, 从而对图$K_{6,3,2*(k-6),1*4}$($k\geq6$)和它们的所有完全$k$--部子图证明了Ohba猜想成立.

英文摘要:

      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.