Ohba's Conjecture (Solved)

Recomm. for undergrads: yes
Posted by: Jon Noel
on: May 18th, 2011
Solved by: Noel, Reed and Wu. Submitted.

\begin{conjecture} If $|V(G)|\leq 2\chi(G)+1$, then $\chi_\ell(G)=\chi(G)$. \end{conjecture}

\section{Basics of List Colouring}

A \emph{$k$-\href[list assignment]{http://en.wikipedia.org/wiki/List_coloring}} of a graph $G$ is an assignment of lists $L(v)$ of $k$ `available colours' to the vertices of $G$. A graph is said to be \emph{$L$-choosable} if it can be properly coloured from the prescribed lists, and \emph{$k$-choosable} if this property holds for every $k$-list assignment.

\begin{definition} Given a graph $G$, we define the \emph{list chromatic number} of $G$ by $\chi_\ell(G)=\min\{k: G \text{ is } k \text{-choosable}\}$. \end{definition}

The lower bound $\chi_\ell(G)\geq\chi(G)$ is easily observed by assigning the same list to every vertex. However, the reverse inequality does not hold in general. In their classic paper [4], Erdos, Rubin and Taylor give the example of $K_{3,3}$ where the three vertices on either side of the bipartition are given lists $\{1,2\},\{2,3\},\{1,3\}$. One may check that no list colouring exists despite the fact that all lists have size two. Note that this example shows that the conjecture, if true, would be tight.

In general, there are bipartite graphs with arbitrarily high list chromatic number and so $\chi_\ell(G)-\chi(G)$ can be arbitrarily large. A natural question arises: \emph{What conditions guarantee that $\chi_\ell(G)=\chi(G)$?} A graph $G$ with this property is said to be \emph{chromatic-choosable}.

\section{The Conjecture}

Erdos, Rubin and Taylor proved that every multipartite graph with all parts of size two is chromatic-choosable [4]. In [12] Gravier and Maffray show that the propertiy still holds if one of the parts has size three. Ohba's Conjecture [1] above can be seen as a generalization. Some weaker versions have been proven:

\begin{theorem}[Ohba $[1]$] If $|V(G)|\leq \chi(G)+\sqrt{2\chi(G)}$, then $G$ is chromatic-choosable. \end{theorem}

\begin{theorem}[Reed and Sudakov $[2]$] If $|V(G)|\leq \frac{5}{3}\chi(G)-\frac{4}{3}$, then $G$ is chromatic-choosable. \end{theorem}

\begin{theorem}[Reed and Sudakov $[3]$] If $|V(G)|\leq (2 − \epsilon)\chi(G)$ where $0 < \epsilon < 1$ and $|V(G)|\geq n_0(\epsilon)$, then $G$ is chromatic-choosable. \end{theorem}

One may observe that Ohba's conjecture holds for all graphs if and only if it holds for complete multipartite graphs. Indeed, given a counterexample we may add an edge between vertices of different colour classes to yeilds another counterexample. Thus, the main focus of [6-11] has been on verifying Ohba's conjecture for certain classes of multipartite graphs. It is now known that complete multipartite graphs having parts of size $\leq5$ satisfy Ohba's conjecture [11]. In other words, the conjecture is solved for graphs with independance number at most five.

Ohba's Conjecture can be found as unsolved problem #50 in Bondy and Murty's book "\href[Graph Theory]{http://books.google.ca/books?id=V0gUTxkOSboC&printsec=frontcover&dq=graph+theory+bondy+and+murty&hl=en&sa=X&ei=VkMaUqP-FcXerQH4iICQBQ&ved=0CC4Q6AEwAA#v=onepage&q=ohba&f=false}" [15].

The problem was recently solved [13]. The proof can be found \href[here]{http://people.maths.ox.ac.uk/noel/Ohba.html}. It can also be found \href[here]{http://people.maths.ox.ac.uk/noel/Masters.pdf}. Click \href[here]{http://www.openproblemgarden.org/op/choice_number_of_k_chromatic_graphs_of_bounded_order} for a problem which generalizes Ohba's Conjecture.


*[1] K. Ohba. On chromatic-choosable graphs, J. Graph Theory. 40 (2002) 130--135. \MRhref{MR1899118}.

[2] B. Reed, B. Sudakov. List colouring when the chromatic number is close to the order of the graph, Combinatorica 25 (1) (2004) 117--123. \MRhref{2109199}.

[3] B. Reed, B. Sudakov. List colouring of graphs with at most $(2 − o(1))\chi$ vertices, Beijing, 2002, in: Proceedings of the International Congress of Mathematicians, vol. III, Higher Ed. Press, Beijing (2002) 587–-603.

[4] P. Erdős, A. L. Rubin, H. Taylor, Choosability in graphs, Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, Congressus Numerantium 26 (1979) 125–-157. \href[pdf]{http://www.math-inst.hu/~p_erdos/1980-07.pdf}.

[6] H. Enomoto, K. Ohba, K. Ota, J. Sakamoto. Choice number of some complete multi-partite graphs, Discrete Math. 244 (1-3) (2002) 55--66.

[7] K. Ohba. Choice number of complete multipartite graphs with part size at most three, Ars Combin. 72 (2004) 133--139.

[8] Y. Shen, W. He, G. Zheng, Y. Wang, L. Zhang. On choosability of some complete multipartite graphs and Ohba's conjecture, Discrete Math. 308 (1) (2008) 136--143.

[9] W. He, L. Zhang, D. W. Cranston, Y. Shen, G. Zheng. Choice number of complete multipartite graphs $K_{3*3,2*(k-5),1*2}$ and $K_{4,3*2,2*(k-6),1*3}$, Discrete Math. 308 (23) (2008) 5871–-5877.

[10] G. Zheng, Y. Shen, Z. Chen, J. Lv. On choosability of complete multipartite graphs $K_{4,3\ast t,2\ast(k-2t-2),1\ast(t+1)}$, Discuss. Math. Graph Theory 30 (2) (2010) 237–-244.

[11] A. V. Kostochka, M. Stiebitz, D. R. Woodall. Ohba's conjecture for graphs with independence number five, Discrete Math. 311 (12) (2011) 996--1005. \href[ScienceDirect]{http://www.sciencedirect.com/science/article/B6V00-52FTPR4-5/2/23424e95b430d984628f2ae9d3bb1548}.

[12] S. Gravier, F. Maffray. Graphs whose choice number is equal to their chromatic number, J. Graph Theory 27 (1998) 87--97. \MRhref{MR1491561}.

[13] J. A. Noel, B. A. Reed, H. Wu. A Proof of a Conjecture of Ohba. Submitted. \href[pdf]{people.maths.ox.ac.uk/noel/Ohba Paper.pdf}.

[14] J. A. Noel. Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond. Master's Thesis, McGill University. \href[pdf]{people.maths.ox.ac.uk/noel/Masters.pdf}.

[15] J. A. Bondy and U. S. R. Murty. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, 2008.

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.