2013/08/30 by Jonathan A. Noel, Noel, Jonathan A., Douglas B. West +5
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.1308.6739
14 pages
openalex publication_date 2013/08/30 · arxiv created 2014/08/27 · arxiv updated 2014/08/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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),\lceil(|V(G)|+χ(G)-1)/3\rceil\. 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).