![](/files/happy5.png)
List Colourings of Complete Multipartite Graphs with 2 Big Parts
![$ a,b\geq2 $](/files/tex/7ae98b0c55d36dcaf7def20925869c5d4b1d48ef.png)
![$ t\geq0 $](/files/tex/13168e3697d72526aed2db7c8042d868fd46bc7e.png)
![$ \chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t) $](/files/tex/bd7ca9e1076d95097ac657d98e06895400a68ec0.png)
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
:
![$ |V(G)|\leq 2\chi(G)+1 $](/files/tex/4a7472498fbaf9edea55531f6e3927a3336b2285.png)
![$ \chi_\ell(G)=\chi(G) $](/files/tex/0a2573f7d1a57016f919f018635cd3f9f9875fc4.png)
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]:
![$ a\geq5 $](/files/tex/ad661851ce414ab43b11b2293ddec61ada28632b.png)
![\[\lfloor \sqrt{a}\rfloor - 1 \leq \phi(a,2)\leq \left\lceil\frac{-7+\sqrt{8a+17}}{2}\right\rceil.\]](/files/tex/d9e6ce2988c5a7ad64ae8cd05c71d9baa3716985.png)
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.