Abstract
A graph is called \emph{chromatic-choosable} if its choice number is equal to its chromatic number, namely . Ohba has conjectured that every graph satisfying is chromatic-choosable. Since each -chromatic graph is a subgraph of a complete -partite graph, we see that Ohba's conjecture is true if and only if it is true for every complete multipartite graph. However, the only complete multipartite graphs for which Ohba's conjecture has been verified are: , , , , and . In this paper, we show that Ohba's conjecture is true for two new classes of complete multipartite graphs: graphs with three parts of size 3 and graphs with one part of size 4 and two parts of size 3. Namely, we prove that and (for and , respectively).
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.