Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond

MaRDI QIDQ6244479zbMATH OpenFDO

Authors Jonathan A. Noel

Publication date 1 September 2013

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: The emph{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)=chi(G)$ whenever $|V(G)|leq2chi(G)+1$. We also prove a strengthening of Ohba's Conjecture which is best possible for graphs on at most $3chi(G)$ vertices, and pose several conjectures related to our work.

This page was built for publication: Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6244479)