Discussiones Mathematicae Graph Theory 32(1) (2012) 31-37
doi: 10.7151/dmgt.1583

[BIBTex] [PDF] [PS]

List Coloring of Complete Multipartite Graphs

Tomáš Vetrík

School of Mathematical Sciences
University of KwaZulu-Natal
Durban, South Africa

Abstract

The choice number of a graph G is the smallest integer k such that for every assignment of a list L(v) of k colors to each vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from L(v). We present upper and lower bounds on the choice number of complete multipartite graphs with partite classes of equal sizes and complete r-partite graphs with r−1 partite classes of order two.

Keywords: list coloring, choice number, complete multipartite graph

2010 Mathematics Subject Classification: 05C15.

References

[1]N. Alon, Choice numbers of graphs; a probabilistic approach, Combinatorics, Probability and Computing 1 (1992) 107--114, doi: 10.1017/S0963548300000122.
[2]H. Enomoto, K. Ohba, K. Ota and J. Sakamoto, Choice number of some complete multi-partite graphs, Discrete Math. 244 (2002) 55--66, doi: 10.1016/S0012-365X(01)00059-0.
[3]P. Erdös, A.L. Rubin and H. Taylor, Choosability in graphs, in: Proceedings of the West-Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, California (Congr. Numer. XXVI, 1979) 125--157.
[4]S. Gravier and F. Maffray, Graphs whose choice number is equal to their chromatic number, J. Graph Theory 27 (1998) 87--97, doi: 10.1002/(SICI)1097-0118(199802)27:2<87::AID-JGT4>3.0.CO;2-B.
[5]H.A. Kierstead, On the choosability of complete multipartite graphs with part size three, Discrete Math. 211 (2000) 255--259, doi: 10.1016/S0012-365X(99)00157-0.
[6]Zs. Tuza, Graph colorings with local constraints --- a survey, Discuss. Math. Graph Theory 17 (1997) 161--228, doi: 10.7151/dmgt.1049.
[7]V.G. Vizing, Coloring the vertices of a graph in prescribed colors, Diskret. Analiz 29 (1976) 3--10 (in Russian).
[8]D.R. Woodall, List colourings of graphs, in: Surveys in Combinatorics, London Mathematical Society Lecture Note Series 288 (Cambridge University Press, 2001) 269--301.
[9]D. Yang, Extension of the game coloring number and some results on the choosability of complete multipartite graphs, PhD Thesis, (Arizona State University 2003).

Received 26 January 2009
Revised 11 January 2011
Accepted 11 January 2011