Importance: Medium ✭✭
 Author(s): Allagan, Julian
 Subject: Graph Theory » Coloring » » Vertex coloring
 Keywords: complete bipartite graph complete multipartite graph list coloring
 Posted by: Jon Noel on: April 12th, 2014
Question   Given , what is the smallest integer such that ?

The list chromatic number of a graph , denoted , is the minimum such that for every assignment of lists of size to the vertices of there is a proper colouring in which every vertex is mapped to a colour in its own list. For more background on the list chromatic number, see [3].

Given graphs and , the join of and , denoted , is obtained by taking disjoint copies of and and adding all edges between them. Ohba [1] proved that for every graph there exists such that . The question above asks to determine the minimum value of in the case that is a complete bipartite graph. It seems that it was first studied in [4], although this is unclear; for the time being, we have chosen to attribute this problem to J. Allagan.

Define to be the minimum such that . Note that, if is a complete multipartite graph with at most one non-singleton part, then we see that by colouring the vertices of the non-singleton part last. Thus, if or is equal to 1, then . As it turns out, and . This can be deduced from the following result of [2] and the fact that :

Theorem  (Noel, Reed, Wu (2012))   If , then .

The above result of [2] implies that if , then . However it seems that, for most values of , this bound is far from tight.

A simple observation is that, since for all , we must have

The following is a result of Allagan [4]:

Theorem  (Allagan (2009))   If , then

This implies that for and that for .

## Bibliography

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

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

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

[4] J. A. D. Allagan. Choice Numbers, Ohba Numbers and Hall Numbers of some complete -partite graphs. PhD Thesis. Auburn University. 2009.

* indicates original appearance(s) of problem.