Name
Abstract | ||
|---|---|---|
Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability ch(G) of G is equal to its chromatic number @g(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.disc.2011.02.026 | Discrete Mathematics |
Keywords | Field | DocType |
choosability,chromatic number,list chromatic number,complete multipartite graph,list coloring,vertex coloring | Complete graph,Discrete mathematics,Combinatorics,Chromatic scale,Vertex (geometry),Graph power,Bound graph,List coloring,Multipartite graph,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
311 | 12 | Discrete Mathematics |
Citations | PageRank | References |
5 | 0.47 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandr V. Kostochka | 1 | 682 | 89.87 |
| Michael Stiebitz | 2 | 207 | 30.08 |
| Douglas R. Woodall | 3 | 191 | 28.57 |