A graph G is said to be chromatic-choosable if ch(G) = χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba’s conjecture is true if and only if it is true for complete multipartite graphs. In this paper we show that Ohba’s conjecture is true for complete multipartite graphs for all integers t ≥ 1 and k ≥ 2t+2, that is, , which extends the results given by Shen et al. (Discrete Math. 308 (2008) 136-143), and given by He et al. (Discrete Math. 308 (2008) 5871-5877).
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1489,
author = {Guo-Ping Zheng and Yu-Fa Shen and Zuo-Li Chen and Jin-Feng Lv},
title = {On choosability of complete multipartite graphs $K\_{4,3*t,2*(k-2t-2),1*(t+1)}$
},
journal = {Discussiones Mathematicae Graph Theory},
volume = {30},
year = {2010},
pages = {237-244},
zbl = {1214.05035},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1489}
}
Guo-Ping Zheng; Yu-Fa Shen; Zuo-Li Chen; Jin-Feng Lv. On choosability of complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$
. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 237-244. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1489/
[000] [1] H. Enotomo, K. Ohba, K. Ota and J. Sakamoto, Choice number of some complete multipartite graphs, Discrete Math. 244 (2002) 55-66, doi: 10.1016/S0012-365X(01)00059-0. | Zbl 0994.05066
[001] [2] P. Erdös, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125-157.
[002] [3] 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 | Zbl 0891.05031
[003] [4] W. He, L. Zhang, Daniel W. Cranston, Y. Shen and G. Zheng, Choice number of complete multipartite graphs and , Discrete Math. 308 (2008) 5871-5877, doi: 10.1016/j.disc.2007.10.046.
[004] [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. | Zbl 0944.05031
[005] [6] K. Ohba, On chromatic choosable graphs, J. Graph Theory 40 (2002) 130-135, doi: 10.1002/jgt.10033. | Zbl 1004.05030
[006] [7] K. Ohba, Choice number of complete multipartite graphs with part size at most three, Ars Combinatoria 72 (2004) 133-139. | Zbl 1078.05032
[007] [8] B. Reed and B. Sudakov, List colouring when the chromatic number is close to the order of the graph, Combinatorica 25 (2005) 117-123, doi: 10.1007/s00493-005-0010-x. | Zbl 1063.05049
[008] [9] Y. Shen, W. He, G. Zheng and Y. Li, Ohba's conjecture is ture for graph with independence number at most three, Applied Mathematics Letters 22 (2009) 938-942, doi: 10.1016/j.aml.2009.01.001. | Zbl 1162.05319
[009] [10] Y. Shen, W. He, G. Zheng, Y. Wang and L. Zhang, On choosability of some complete multipartite graphs and Ohba's conjecture, Discrete Math. 308 (2008) 136-143, doi: 10.1016/j.disc.2007.03.059. | Zbl 1136.05021
[010] [11] Y. Shen, G. Zheng and W. He, Chromatic choosability of a class of complete multipartite graphs, J. Mathematical Research and Exposition 27 (2007) 264-272. | Zbl 1157.05025
[011] [12] Zs. Tuza, Graph colorings with local constrains-A survey, Discuss. Math. Graph Theory 17 (1997) 161-228, doi: 10.7151/dmgt.1049. | Zbl 0923.05027
[012] [13] V.G. Vizing, Coloring the vertices of a graph in prescribed colors (in Russian), Diskret. Anal. 29 (1976) 3-10.
[013] [14] D.R. Woodall, List colourings of graphs, in: J.W.P. Hirschfeld (ed.), Surveys in Combinatorics, 2001, London Math. Soc. Lecture Note Series, vol. 288 (Cambridge University Press, Cambridge, UK, 2001) 269-301. | Zbl 0979.05047