Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648163 | Discrete Mathematics | 2011 | 10 Pages |
Abstract
Ohba has conjectured that if GG is a kk-chromatic graph with at most 2k+12k+1 vertices, then the list chromatic number or choosability ch(G) of GG is equal to its chromatic number χ(G)χ(G), which is kk. It is known that this holds if GG has independence number at most three. It is proved here that it holds if GG has independence number at most five. In particular, and equivalently, it holds if GG is a complete kk-partite graph and each part has at most five vertices.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Alexandr V. Kostochka, Michael Stiebitz, Douglas R. Woodall,