Article ID Journal Published Year Pages File Type
4650104 Discrete Mathematics 2008 8 Pages PDF
Abstract

A graph G   is said to be chromatic-choosable if ch(G)=χ(G)ch(G)=χ(G). Ohba has conjectured that every graph G   with 2χ(G)+12χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba's conjecture is true if and only if it is true for complete multipartite graphs. But for complete multipartite graphs, the graphs for which Ohba's conjecture has been verified are nothing more than K3*2,2*(k-3),1K3*2,2*(k-3),1, K3,2*(k-1)K3,2*(k-1), and Ks+3,2*(k-s-1),1*sKs+3,2*(k-s-1),1*s. These results have been obtained indirectly from the investigation about complete multipartite graphs by Gravier and Maffray and by Enomoto et al. In this paper we show that Ohba's conjecture is true for complete multipartite graphs K4,3,2*(k-4),1*2K4,3,2*(k-4),1*2 and K5,3,2*(k-5),1*3K5,3,2*(k-5),1*3. By the way, we give some discussions about a result of Enomoto et al.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , ,