List colouring of graphs with at most $(2-o(1))\chi$ vertices

Abstract

Ohba has conjectured \cite{ohb} that if the graph $G$ has $2\chi (G)+1$ or fewer vertices then the list chromatic number and chromatic number of $G$ are equal. In this paper we prove that this conjecture is asymptotically correct. More precisely we obtain that for any $0<\epsilon <1$, there exist an $n_0=n_0(\epsilon )$ such that the list chromatic number of $G$ equals its chromatic number, provided $$n_0\le |V(G)|\le (2-\epsilon )\chi (G).$$