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

Let ch(G)ch(G) denote the choice number of a graph GG (also called “list chromatic number” or “choosability” of GG). Noel, Reed, and Wu proved the conjecture of Ohba that ch(G)=χ(G)ch(G)=χ(G) when |V(G)|≤2χ(G)+1|V(G)|≤2χ(G)+1. We extend this to a general upper bound: ch(G)≤max{χ(G),⌈(|V(G)|+χ(G)−1)/3⌉}ch(G)≤max{χ(G),⌈(|V(G)|+χ(G)−1)/3⌉}. Our result is sharp for |V(G)|≤3χ(G)|V(G)|≤3χ(G) using Ohba’s examples, and it improves the best-known upper bound for ch(K4,…,4)ch(K4,…,4).