Importance: Low ✭
 Author(s):
 Subject: Graph Theory » Coloring » » Vertex coloring
 Keywords: choosability complete multipartite graph list coloring
 Posted by: Jon Noel on: April 11th, 2013
 Solved by: H. A. Kierstead, A. Salmon and R. Wang

\begin{question} What is the choice number of $K_{4*k}$ for general $k$? \end{question}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

For positive integers $m$ and $k$, let $K_{m*k}$ be the complete $k$-partite graph in which every part has size $m$. For the definition of the choice number (list chromatic number) see the \Def[Wikipedia page]{List_coloring}.

Determining the choice number of $K_{m*k}$ seems to be a natural first step to obtaining a general bound on the choice number of graphs on a bounded number of vertices.

An old result of Erdos, Rubin and Taylor [ERT80] is that the choice number of $K_{2*k}$ is $k$. Ohba [Ohb02] conjectured a generalization of this result which was proved by Noel, Reed and Wu [NRW12] (also see [Noe13]): \emph{if $|V(G)|\leq 2\chi(G)+1$, then the choice number of $G$ is $\chi(G)$.}

Kierstead [Kier00] proved that the choice number of $K_{3*k}$ is exactly $\left\lceil\frac{4k-1}{3}\right\rceil$. The upper bound was generalized by Noel, West, Wu and Zhu [NWWZ13] to the following: \emph{if $|V(G)|\leq 3\chi(G)$, then the choice number of $G$ is at most $\left\lceil\frac{4\chi(G)-1}{3}\right\rceil$.}

More generally, Noel et al. [NWWZ13] proved that, for any graph $G$, the choice number of $G$ is at most $\left\lceil\frac{|V(G)|+\chi(G)-1}{3}\right\rceil$ (also see [Noe13]). This implies the following:

\begin{theorem}[Noel et al. 2013] The choice number of $K_{4*k}$ is at most $\left\lceil\frac{5k-1}{3}\right\rceil$. \end{theorem}

A lower bound on the choice number of $K_{4*k}$ is given by Yang [Yan03]:

\begin{theorem}[Yang 2003] The choice number of $K_{4*k}$ is at least $\left\lfloor\frac{3k}{2}\right\rfloor$. \end{theorem}

The problem was recently solved by Kierstead, Salmon and Wang [KSW14]. They proved that, surprisingly, the lower bound $\left\lfloor\frac{3k}{2}\right\rfloor$ is tight for all $k$.

\begin{theorem}[Kierstead, Salmon and Wang 2014] The choice number of $K_{4*k}$ is equal to $\left\lceil\frac{3k-1}{2}\right\rceil$. \end{theorem}

Naturally, we wonder whether this result can be generalised to all graphs on at most $\chi(G)$ vertices. See \href[this]{http://www.openproblemgarden.org/op/choice_number_of_k_chromatic_graphs_of_bounded_order} posting as well.

\begin{question} Is it true that if $|V(G)|\leq 4\chi(G)$, then $\text{ch}(G)\leq \left\lceil\frac{3\chi(G)-1}{2}\right\rceil$? \end{question}

## Bibliography

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

[ERT80] P. Erdos, A. L. Rubin, and H. Taylor. Choosability in graphs. Congress. Numer., XXVI, pages 125–157, 1980.

[Kie00] H. A. Kierstead. On the choosability of complete multipartite graphs with part size three. Discrete Math., 211(1-3):255–259, 2000.

[KSW14] H. A. Kierstead, A. Salmon and R. Wang. \arxiv[On the Choice Number of Complete Multipartite Graphs With Part Size Four]{1407.3817}.

[Noe13] J. A. Noel. Choosability of Graphs With Bounded Order: Ohba's Conjecture and Beyond. Master's thesis, McGill University, Montreal. \href[pdf]{http://people.maths.ox.ac.uk/noel/Masters.pdf}

[NRW12] J. A. Noel, B. A. Reed, and H. Wu. A Proof of a Conjecture of Ohba. Preprint, arXiv:1211.1999v1, November 2012. \href[Webpage]{http://people.maths.ox.ac.uk/noel/Ohba.html}

[NWWZ13] J. A. Noel, D. B. West, H. Wu, and X. Zhu. Beyond Ohba's Conjecture: A bound on the choice number of $k$-chromatic graphs with $n$ vertices. Preprint, arXiv:1308.6739v1, August 2013. \href[pdf]{http://people.maths.ox.ac.uk/noel/ohbagen.pdf}

[Ohb02] K. Ohba. On chromatic-choosable graphs. J. Graph Theory, 40(2):130–135, 2002.

[Yan03] D. Yang. Extension of the game coloring number and some results on the choosability of complete multipartite graphs. PhD thesis, Arizona State University, Tempe, Arizona, 2003.

* indicates original appearance(s) of problem.