# List Colourings of Complete Multipartite Graphs with 2 Big Parts

**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.