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

Let 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 ch(G) = χ(G) when |V (G) | ≤ 2χ(G) + 1. We extend this to a general upper bound: ch(G) ≤ max{χ(G), ⌈(|V (G) | + χ(G) − 1)/3⌉}. Our result is sharp for |V (G) | ≤ 3χ(G) using Ohba’s examples, and it improves the best-known upper bound for ch(K4,...,4)