
arXiv: 1308.3046
A graph $G$ is called \emph{chromatic-choosable} if its choice number is equal to its chromatic number, namely $Ch(G)=��(G)$. Ohba has conjectured that every graph $G$ satisfying $|V(G)|\leq 2��(G)+1$ is chromatic-choosable. Since each $k$-chromatic graph is a subgraph of a complete $k$-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: $K_{3*2,2*(k-3),1}$, $K_{3,2*(k-1)}$, $K_{s+3,2*(k-s-1),1*s}$, $K_{4,3,2*(k-4),1*2}$, and $K_{5,3,2*(k-5),1*3}$. 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 $Ch(K_{3*3,2*(k-5),1*2})=k$ and $Ch(K_{4,3*2,2*(k-6),1*3})=k$ (for $k\geq 5$ and $k\geq 6$, respectively).
10 pages; this paper proves 2 special cases of Ohba's Conjecture, which has now been proved completely: http://arxiv.org/abs/1211.1999
list coloring, Coloring of graphs and hypergraphs, Ohba's conjecture, FOS: Mathematics, Chromatic choosable graphs, Mathematics - Combinatorics, Combinatorics (math.CO), complete multipartite graphs, Complete multipartite graphs, chromatic choosable graphs, List coloring, Ohba’s conjecture
list coloring, Coloring of graphs and hypergraphs, Ohba's conjecture, FOS: Mathematics, Chromatic choosable graphs, Mathematics - Combinatorics, Combinatorics (math.CO), complete multipartite graphs, Complete multipartite graphs, chromatic choosable graphs, List coloring, Ohba’s conjecture
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
