List coloring of complete multipartite graphs
Discussiones Mathematicae Graph Theory (2012)
- Volume: 32, Issue: 1, page 31-37
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topTomáš Vetrík. "List coloring of complete multipartite graphs." Discussiones Mathematicae Graph Theory 32.1 (2012): 31-37. <http://eudml.org/doc/270922>.
@article{TomášVetrík2012,
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.},
author = {Tomáš Vetrík},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {list coloring; choice number; complete multipartite graph},
language = {eng},
number = {1},
pages = {31-37},
title = {List coloring of complete multipartite graphs},
url = {http://eudml.org/doc/270922},
volume = {32},
year = {2012},
}
TY - JOUR
AU - Tomáš Vetrík
TI - List coloring of complete multipartite graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 1
SP - 31
EP - 37
AB - 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.
LA - eng
KW - list coloring; choice number; complete multipartite graph
UR - http://eudml.org/doc/270922
ER -
References
top- [1] N. Alon, Choice numbers of graphs; a probabilistic approach, Combinatorics, Probability and Computing 1 (1992) 107-114, doi: 10.1017/S0963548300000122. Zbl0793.05076
- [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. Zbl0994.05066
- [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 Zbl0891.05031
- [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. Zbl0944.05031
- [6] Zs. Tuza, Graph colorings with local constraints -- a survey, Discuss. Math. Graph Theory 17 (1997) 161-228, doi: 10.7151/dmgt.1049. Zbl0923.05027
- [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. Zbl0979.05047
- [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).
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.