Home » Subject » Graph Theory » Coloring » Vertex coloring
Importance: Low ✭
Author(s):
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: choosability
complete multipartite graph
list coloring
Recomm. for undergrads: yes
Posted by: Jon Noel
on: April 11th, 2013
Solved by: H. A. Kierstead, A. Salmon and R. Wang
Question   What is the choice number of $ K_{4*k} $ for general $ k $?

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 Wikipedia page.

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]): 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: if $ |V(G)|\leq 3\chi(G) $, then the choice number of $ G $ is at most TeX Embedding failed!.}

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:

Theorem  (Noel et al. 2013)   The choice number of $ K_{4*k} $ is at most $ \left\lceil\frac{5k-1}{3}\right\rceil $.

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

Theorem  (Yang 2003)   The choice number of $ K_{4*k} $ is at least $ \left\lfloor\frac{3k}{2}\right\rfloor $.

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

Theorem  (Kierstead, Salmon and Wang 2014)   The choice number of $ K_{4*k} $ is equal to $ \left\lceil\frac{3k-1}{2}\right\rceil $.

Naturally, we wonder whether this result can be generalised to all graphs on at most $ \chi(G) $ vertices. See this posting as well.

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 $?

Related problems

Choice Number of k-Chromatic Graphs of Bounded Order
Ohba's Conjecture

Bibliography

[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. On the Choice Number of Complete Multipartite Graphs With Part Size Four.

[Noe13] J. A. Noel. Choosability of Graphs With Bounded Order: Ohba's Conjecture and Beyond. Master's thesis, McGill University, Montreal. pdf

[NRW12] J. A. Noel, B. A. Reed, and H. Wu. A Proof of a Conjecture of Ohba. Preprint, arXiv:1211.1999v1, November 2012. Webpage

[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. 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.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options