PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 30 | 2 | 237-244
Tytuł artykułu

On choosability of complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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).
Wydawca
Rocznik
Tom
30
Numer
2
Strony
237-244
Opis fizyczny
Daty
wydano
2010
otrzymano
2009-01-22
poprawiono
2009-06-22
zaakceptowano
2009-06-22
Twórcy
  • School of Mathematics and Information Science and Technology, Hebei Normal University of Science and Technology, Qinhuangdao 066004, P.R. China
  • Center for Mathematics of Hebei Province, Hebei Normal University, Shijiazhuang 050016, P.R. China
autor
  • School of Mathematics and Information Science and Technology, Hebei Normal University of Science and Technology, Qinhuangdao 066004, P.R. China
  • Center for Mathematics of Hebei Province, Hebei Normal University, Shijiazhuang 050016, P.R. China
autor
  • School of Mathematics and Information Science and Technology, Hebei Normal University of Science and Technology, Qinhuangdao 066004, P.R. China
  • Center for Mathematics of Hebei Province, Hebei Normal University, Shijiazhuang 050016, P.R. China
autor
  • School of Mathematics and Information Science and Technology, Hebei Normal University of Science and Technology, Qinhuangdao 066004, P.R. China
  • Center for Mathematics of Hebei Province, Hebei Normal University, Shijiazhuang 050016, P.R. China
Bibliografia
  • [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.
  • [2] P. Erdös, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125-157.
  • [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
  • [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] 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] K. Ohba, On chromatic choosable graphs, J. Graph Theory 40 (2002) 130-135, doi: 10.1002/jgt.10033.
  • [7] K. Ohba, Choice number of complete multipartite graphs with part size at most three, Ars Combinatoria 72 (2004) 133-139.
  • [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.
  • [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.
  • [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.
  • [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.
  • [12] Zs. Tuza, Graph colorings with local constrains-A survey, Discuss. Math. Graph Theory 17 (1997) 161-228, doi: 10.7151/dmgt.1049.
  • [13] V.G. Vizing, Coloring the vertices of a graph in prescribed colors (in Russian), Diskret. Anal. 29 (1976) 3-10.
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1489
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.