2013/01/01 by Jonathan A. Noel, Noel, Jonathan A.
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.1309.0225
Master's Thesis, McGill University
openalex publication_date 2013/01/01 · arxiv created 2013/09/01 · arxiv updated 2013/09/03 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
The choice number of a graph G, denoted \ch(G), is the minimum integer k such that for any assignment of lists of size k to the vertices of G, there is a proper colouring of G such that every vertex is mapped to a colour in its list. For general graphs, the choice number is not bounded above by a function of the chromatic number. In this thesis, we prove a conjecture of Ohba which asserts that \ch(G)=χ(G) whenever |V(G)|≤ 2χ(G)+1. We also prove a strengthening of Ohba's Conjecture which is best possible for graphs on at most 3χ(G) vertices, and pose several conjectures related to our work.