Open Problem Garden

Importance: Medium ✭✭

Author(s):

Subject:	Graph Theory
	» Coloring
	» » Vertex coloring

Keywords:	choosability
	chromatic number
	complete multipartite graph
	list coloring

Recomm. for undergrads: yes

Posted	by:	Jon Noel
	on:	May 18th, 2011

Solved by:

Noel, Reed and Wu. Submitted.

Conjecture If $|V(G)|\leq 2\chi(G)+1$ , then $\chi_\ell(G)=\chi(G)$ .

Basics of List Colouring

A $k$ -list assignment 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 $L$ -choosable if it can be properly coloured from the prescribed lists, and $k$ -choosable if this property holds for every $k$ -list assignment.

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

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: What conditions guarantee that $\chi_\ell(G)=\chi(G)$ ? A graph $G$ with this property is said to be chromatic-choosable.

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:

Theorem (Ohba $[1)</b>  $ ] If $|V(G)|\leq \chi(G)+\sqrt{2\chi(G)}$ , then $G$ is chromatic-choosable.

Theorem (Reed and Sudakov $[2)</b>  $ ] If $|V(G)|\leq \frac{5}{3}\chi(G)-\frac{4}{3}$ , then $G$ is chromatic-choosable.

Theorem (Reed and Sudakov $[3)</b>  $ ] If $|V(G)|\leq (2 − \epsilon)\chi(G)$ where $0 < \epsilon < 1$ and $|V(G)|\geq n_0(\epsilon)$ , then $G$ is chromatic-choosable.

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 "Graph Theory" [15].

The problem was recently solved [13]. The proof can be found here. It can also be found here. Click here for a problem which generalizes Ohba's Conjecture.

Related problems
Edge list coloring conjecture
Choice Number of k-Chromatic Graphs of Bounded Order
On-Line Ohba's Conjecture
Bounding the on-line choice number in terms of the choice number

Bibliography

*[1] K. Ohba. On chromatic-choosable graphs, J. Graph Theory. 40 (2002) 130--135. MathSciNet.

[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. MathSciNet.

[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. 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. ScienceDirect.

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

[13] J. A. Noel, B. A. Reed, H. Wu. A Proof of a Conjecture of Ohba. Submitted. pdf.

[14] J. A. Noel. Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond. Master's Thesis, McGill University. pdf.

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

* indicates original appearance(s) of problem.