PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 3 | 577-584
Tytuł artykułu

On the Independence Number of Edge Chromatic Critical Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤ [...] . It is known that α (G) < [...] |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤ [...] |V | when △ ≥ 5 and n2 ≤ 2(△− 1)
Wydawca
Rocznik
Tom
34
Numer
3
Strony
577-584
Opis fizyczny
Daty
wydano
2014-08-01
otrzymano
2012-12-22
poprawiono
2013-05-11
zaakceptowano
2013-07-11
online
2014-07-16
Twórcy
autor
  • School of Science, China University of Mining and Technology Xuzhou, Jiangsu, 221008, P.R.China, 615595479@qq.com
autor
  • School of Science, China University of Mining and Technology Xuzhou, Jiangsu, 221008, P.R.China, 2408955057@qq.com
autor
  • Department of Mathematics, Jiangsu Normal University, Xuzhou, Jiangsu, 221116, P.R.China, zkmiao@163.com
Bibliografia
  • 1] G. Brinkmann, S.A. Choudum, S. Gr¨unewald and E. Steffen, Bounds for the inde- pendence number of critical graphs, Bull. London Math. Soc. 32 (2000) 137-140. doi:10.1112/S0024609399006645[Crossref]
  • [2] S. Grünewald and E. Steffen, Independent sets and 2-factors in edge chromatic crit- ical graphs, J. Graph Theory 45 (2004) 113-118. doi:10.1002/jgt.10141[Crossref]
  • [3] R. Luo and Y. Zhao, A note on Vizing’s independence number conjecture of edge chromatic critical graphs, Discrete Math. 306 (2006) 1788-1790. doi:10.1016/j.disc.2006.03.040[WoS][Crossref]
  • [4] R. Luo and Y. Zhao, An application of Vizing and Vizing-like adjacency lemmas to Vizing’s independence number conjecture of edge chromatic critical graphs, Discrete Math. 309 (2009) 2925-2929. doi:10.1016/j.disc.2008.06.019[Crossref][WoS]
  • [5] R. Luo, L.Y. Miao and Y. Zhao, The size of edge chromatic critical graphs with maximum degree 6, J. Graph Theory 60 (2009) 149-171. doi:10.1002/jgt.20351[Crossref]
  • [6] L.Y. Miao, On the independence number of edge chromatic critical graphs, Ars Combin. 98 (2011) 471-481.
  • [7] D.P. Sanders and Y. Zhao, Planar graphs with maximum degree seven are Class I, J. Combin. Theory (B) 83 (2001) 201-212. doi:0.1006/jctb.2001.2047
  • [8] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian).
  • [9] V.G. Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk 23 (1968) 117-134, Russian Math. Surveys 23 (1968) 125-142. doi:10.1070/RM1968v023n06ABEH001252[Crossref]
  • [10] D.R. Woodall, The independence number of an edge chromatic critical graph, J. Graph Theory 66 (2011) 98-103. doi:10.1002/jgt.20493[Crossref]
  • [11] D.R. Woodall, The average degree of an edge-chromatic critical graph II, J. Graph Theory 56 (2007) 194-218. doi:10.1002/jgt.20259[Crossref]
  • [12] H.P. Yap, Some Topics in Graph Theory, London Math. Soc. Lecture Notes Ser. Vol. 108 (Cambridge Univ. Press, 1986). doi:10.1017/CBO9780511662065[Crossref]
  • [13] L. Zhang, Every planar graph with maximum degree 7 is of class 1, Graphs Combin. 16 (2000) 467-495. doi:10.1007/s003730070009[Crossref]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1753
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ć.