A Proof of a Conjecture of Ohba

Abstract

We prove a conjecture of Ohba which says that every graph $G$ on at most $2\chi (G)+1$ vertices satisfies ${\chi }_{\ell }(G)=\chi (G)$.

21 pages

References in corpus (4)

• A note on list-coloring powers of graphs
• Beyond Ohba's Conjecture: A bound on the choice number of $k$-chromatic graphs with $n$ vertices
• Counterexamples to the List Square Coloring Conjecture
• Chromatic-choosability of the power of graphs

Cited by in corpus (3)

• Beyond Ohba's Conjecture: A bound on the choice number of $k$-chromatic graphs with $n$ vertices
• List Colouring Big Graphs On-Line
• Partial list colouring of certain graphs