On the Independence Number of Edge Chromatic Critical Graphs

• Autorzy: Shiyou Pang , Lianying Miao , Wenyao Song , Zhengke Miao
• 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)

Słowa kluczowe

EN

edge coloring; edge-chromatic critical graphs; independence number

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 3
• Strony: 577-584

Daty

wydano

2014-08-01

otrzymano

2012-12-22

poprawiono

2013-05-11

zaakceptowano

2013-07-11

online

2014-07-16

Twórcy

autor

Shiyou Pang

• School of Science, China University of Mining and Technology Xuzhou, Jiangsu, 221008, P.R.China

autor

Lianying Miao

• Department of Mathematics, Jiangsu Normal University, Xuzhou, Jiangsu, 221116, P.R.China

autor

Wenyao Song

• School of Science, China University of Mining and Technology Xuzhou, Jiangsu, 221008, P.R.China

autor

Zhengke Miao

• Department of Mathematics, Jiangsu Normal University, Xuzhou, Jiangsu, 221116, P.R.China

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]

Identyfikatory

DOI

10.7151/dmgt.1753