On choosability of complete multipartite graphs K 4 , 3 * t , 2 * ( k - 2 t - 2 ) , 1 * ( t + 1 )

Guo-Ping Zheng; Yu-Fa Shen; Zuo-Li Chen; Jin-Feng Lv

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 2, page 237-244
  • ISSN: 2083-5892

Abstract

top
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 K 4 , 3 * t , 2 * ( k - 2 t - 2 ) , 1 * ( t + 1 ) for all integers t ≥ 1 and k ≥ 2t+2, that is, c h ( K 4 , 3 * t , 2 * ( k - 2 t - 2 ) , 1 * ( t + 1 ) ) = k , which extends the results c h ( K 4 , 3 , 2 * ( k - 4 ) , 1 * 2 ) = k given by Shen et al. (Discrete Math. 308 (2008) 136-143), and c h ( K 4 , 3 * 2 , 2 * ( k - 6 ) , 1 * 3 ) = k given by He et al. (Discrete Math. 308 (2008) 5871-5877).

How to cite

top

Guo-Ping Zheng, et al. "On choosability of complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$." Discussiones Mathematicae Graph Theory 30.2 (2010): 237-244. <http://eudml.org/doc/270817>.

@article{Guo2010,
abstract = {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 $K_\{4,3*t,2*(k-2t-2),1*(t+1)\}$ for all integers t ≥ 1 and k ≥ 2t+2, that is, $ch(K_\{4,3*t,2*(k-2t-2),1*(t+1)\}) = k$, which extends the results $ch(K_\{4,3,2*(k-4),1*2\}) = k$ given by Shen et al. (Discrete Math. 308 (2008) 136-143), and $ch(K_\{4,3*2,2*(k-6),1*3\}) = k$ given by He et al. (Discrete Math. 308 (2008) 5871-5877).},
author = {Guo-Ping Zheng, Yu-Fa Shen, Zuo-Li Chen, Jin-Feng Lv},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {list coloring; complete multipartite graphs; chromatic-choosable graphs; Ohba's conjecture},
language = {eng},
number = {2},
pages = {237-244},
title = {On choosability of complete multipartite graphs $K_\{4,3*t,2*(k-2t-2),1*(t+1)\}$},
url = {http://eudml.org/doc/270817},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Guo-Ping Zheng
AU - Yu-Fa Shen
AU - Zuo-Li Chen
AU - Jin-Feng Lv
TI - On choosability of complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 2
SP - 237
EP - 244
AB - 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 $K_{4,3*t,2*(k-2t-2),1*(t+1)}$ for all integers t ≥ 1 and k ≥ 2t+2, that is, $ch(K_{4,3*t,2*(k-2t-2),1*(t+1)}) = k$, which extends the results $ch(K_{4,3,2*(k-4),1*2}) = k$ given by Shen et al. (Discrete Math. 308 (2008) 136-143), and $ch(K_{4,3*2,2*(k-6),1*3}) = k$ given by He et al. (Discrete Math. 308 (2008) 5871-5877).
LA - eng
KW - list coloring; complete multipartite graphs; chromatic-choosable graphs; Ohba's conjecture
UR - http://eudml.org/doc/270817
ER -

References

top
  1. [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. Zbl0994.05066
  2. [2] P. Erdös, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125-157. 
  3. [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 Zbl0891.05031
  4. [4] W. He, L. Zhang, Daniel W. Cranston, Y. Shen and G. Zheng, Choice number of complete multipartite graphs K 3 * 3 , 2 * ( k - 5 ) , 1 * 2 and K 4 , 3 * 2 , 2 * ( k - 6 ) , 1 * 3 , Discrete Math. 308 (2008) 5871-5877, doi: 10.1016/j.disc.2007.10.046. 
  5. [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. [6] K. Ohba, On chromatic choosable graphs, J. Graph Theory 40 (2002) 130-135, doi: 10.1002/jgt.10033. Zbl1004.05030
  7. [7] K. Ohba, Choice number of complete multipartite graphs with part size at most three, Ars Combinatoria 72 (2004) 133-139. Zbl1078.05032
  8. [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. Zbl1063.05049
  9. [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. Zbl1162.05319
  10. [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. Zbl1136.05021
  11. [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. Zbl1157.05025
  12. [12] Zs. Tuza, Graph colorings with local constrains-A survey, Discuss. Math. Graph Theory 17 (1997) 161-228, doi: 10.7151/dmgt.1049. Zbl0923.05027
  13. [13] V.G. Vizing, Coloring the vertices of a graph in prescribed colors (in Russian), Diskret. Anal. 29 (1976) 3-10. 
  14. [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. Zbl0979.05047

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.