PDF
Discussiones Mathematicae Graph Theory 32(1) (2012)
31-37
DOI: https://doi.org/10.7151/dmgt.1583
List Coloring of Complete Multipartite Graphs
Tomáš Vetrík
School of Mathematical Sciences |
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
Close