List Colourings of Complete Multipartite Graphs with 2 Big Parts

Recomm. for undergrads: yes
Posted by: Jon Noel
on: April 12th, 2014

\begin{question} Given $a,b\geq2$, what is the smallest integer $t\geq0$ such that $\chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t)$? \end{question}

The \emph{list chromatic number} of a graph $G$, denoted $\chi_\ell(G)$, is the minimum $k$ such that for every assignment of lists of size $k$ to the vertices of $G$ 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 $G$ and $H$, the \emph{join} of $G$ and $H$, denoted $G+H$, is obtained by taking disjoint copies of $G$ and $H$ and adding all edges between them. Ohba [1] proved that for every graph $G$ there exists $t\geq0$ such that $\chi_\ell(G+K_t)= \chi(G+K_t)$. The question above asks to determine the minimum value of $t$ in the case that $G$ 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 $\phi(a,b)$ to be the minimum $t$ such that $\chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t)$. Note that, if $G$ is a complete multipartite graph with at most one non-singleton part, then we see that $\chi_\ell(G)=\chi(G)$ by colouring the vertices of the non-singleton part last. Thus, if $a$ or $b$ is equal to 1, then $\phi(a,b)=0$. As it turns out, $\phi(2,2)=\phi(2,3)=0$ and $\phi(3,3)=\phi(2,4)=1$. This can be deduced from the following result of [2] and the fact that $\chi_\ell(K_{3,3})=\chi_\ell(K_{4,2})=3$:

\begin{theorem}[Noel, Reed, Wu (2012)] If $|V(G)|\leq 2\chi(G)+1$, then $\chi_\ell(G)=\chi(G)$. \end{theorem}

The above result of [2] implies that if $a+b\geq 5$, then $\phi(a,b)\leq a+b-5$. However it seems that, for most values of $a,b$, this bound is far from tight.

A simple observation is that, since $\chi_\ell(K_{a,b}+K_t)\geq \chi_\ell(K_{a,b})$ for all $t$, we must have \[\phi(a,b)\geq \chi_\ell(K_{a,b}) - \chi(K_{a,b}) = \chi_\ell(K_{a,b}) -2.\]

The following is a result of Allagan [4]: \begin{theorem}[Allagan (2009)] If $a\geq5$, then \[\lfloor \sqrt{a}\rfloor - 1 \leq \phi(a,2)\leq \left\lceil\frac{-7+\sqrt{8a+17}}{2}\right\rceil.\] \end{theorem}

This implies that $\phi(a,2)=1$ for $4\leq a\leq 8$ and that $\phi(a,2)=2$ for $9\leq a\leq 13$.


% 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)

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

[2] J. A. Noel, B. A. Reed, H. Wu. A Proof of a Conjecture of Ohba. Submitted. \href[pdf]{ Paper.pdf}.

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

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

* indicates original appearance(s) of problem.