| Chromatic Choosability of a Class of Complete Multipartite Graphs |
| Received:August 12, 2005 Revised:November 27, 2005 |
| Key Words:
list coloring complete multipartite graph chromatic choosable graph Ohba's conjecture.
|
| Fund Project:the Science Foundation of the Education Department of Hebei Province (2005108). |
| Author Name | Affiliation | | SHEN Yu-fa | Dept. of Math. & Phys., Hebei Normal University of Sci. & Tech., Qinhuangdao 066004, China
College of Math. \& Info. Sci., Hebei Normal University, Shijiazhuang 050016, China | | ZHENG Guo-ping | Dept. of Math. & Phys., Hebei Normal University of Sci. & Tech., Qinhuangdao 066004, China | | HE Wen-jie | Applied Mathematics Institute, Hebei University of Technology, Tianjin 300130, China |
|
| Hits: 3046 |
| Download times: 1941 |
| Abstract: |
| 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. |
| Citation: |
| DOI:10.3770/j.issn:1000-341X.2007.02.006 |
| View Full Text View/Add Comment |
|
|
|
