On the Independence Number of Edge Chromatic Critical Graphs
Shiyou Pang ; Lianying Miao ; Wenyao Song ; Zhengke Miao
Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 577-584 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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)

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:268142 
@article{bwmeta1.element.doi-10_7151_dmgt_1753,
     author = {Shiyou Pang and Lianying Miao and Wenyao Song and Zhengke Miao},
     title = {On the Independence Number of Edge Chromatic Critical Graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {34},
     year = {2014},
     pages = {577-584},
     zbl = {1295.05179},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1753}
}

Shiyou Pang; Lianying Miao; Wenyao Song; Zhengke Miao. On the Independence Number of Edge Chromatic Critical Graphs. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 577-584. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1753/

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] | Zbl 1033.05041

[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] | Zbl 1200.05114

[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. | Zbl 1249.05289

[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 | Zbl 1024.05031

[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] | Zbl 1216.05040

[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] | Zbl 1137.05037

[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] | Zbl 0588.05002

[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] | Zbl 0988.05042