Beyond Ohba's Conjecture: A bound on the choice number of $k$-chromatic graphs with $n$ vertices

Abstract

Let $\text{ch}(G)$ denote the choice number of a graph $G$ (also called "list chromatic number" or "choosability" of $G$). Noel, Reed, and Wu proved the conjecture of Ohba that $\text{ch}(G)=\chi (G)$ when $|V(G)|\le 2\chi (G)+1$. We extend this to a general upper bound: $\text{ch}(G)\le \max \{\chi (G),\lceil (|V(G)|+\chi (G)-1)/3\rceil \}$. Our result is sharp for $|V(G)|\le 3\chi (G)$ using Ohba's examples, and it improves the best-known upper bound for $\text{ch}(K_{4,\dots ,4})$.

14 pages

References in corpus (3)

• A Proof of a Conjecture of Ohba
• On the choice number of complete multipartite graphs with part size four
• Coloring graphs with dense neighborhoods

Cited by in corpus (1)

• A Proof of a Conjecture of Ohba