Geodesic
On the independence number of edge chromatic critical graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 577-584.

Voir la notice de l'article provenant de la source Library of Science

In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α(G), α(G) ≤ |V|/2. It is known that α(G) lt; 3∆−2/5∆−2|V|. In this paper we improve this bound when △≥4. Our precise result depends on the number n_2 of 2-vertices in G, but in particular we prove that α(G) ≤3∆−3/5∆−3|V| when △≥5 and n_2≤2(△− 1).
Keywords: edge coloring, edge-chromatic critical graphs, independence number 
@article{DMGT_2014_34_3_a9,
     author = {Pang, Shiyou and Miao, Lianying and Song, Wenyao and Miao, Zhengke},
     title = {On the independence number of edge chromatic critical graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {577--584},
     publisher = {mathdoc},
     volume = {34},
     number = {3},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a9/}
}
TY  - JOUR
AU  - Pang, Shiyou
AU  - Miao, Lianying
AU  - Song, Wenyao
AU  - Miao, Zhengke
TI  - On the independence number of edge chromatic critical graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 577
EP  - 584
VL  - 34
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a9/
LA  - en
ID  - DMGT_2014_34_3_a9
ER  - 
%0 Journal Article
%A Pang, Shiyou
%A Miao, Lianying
%A Song, Wenyao
%A Miao, Zhengke
%T On the independence number of edge chromatic critical graphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 577-584
%V 34
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a9/
%G en
%F DMGT_2014_34_3_a9
Pang, Shiyou; Miao, Lianying; Song, Wenyao; Miao, Zhengke. On the independence number of edge chromatic critical graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 577-584. http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a9/

[1] G. Brinkmann, S.A. Choudum, S. Grünewald and E. Steffen, Bounds for the independence number of critical graphs, Bull. London Math. Soc. 32 (2000) 137-140. doi:10.1112/S0024609399006645

[2] S. Grünewald and E. Steffen, Independent sets and 2-factors in edge chromatic critical graphs, J. Graph Theory 45 (2004) 113-118. doi:10.1002/jgt.10141

[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

[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

[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

[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

[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

[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

[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

[13] L. Zhang, Every planar graph with maximum degree 7 is of class 1, Graphs Combin. 16 (2000) 467-495. doi:10.1007/s003730070009