On the Independence Number of Edge Chromatic Critical Graphs

Shiyou Pang; Lianying Miao; Wenyao Song; Zhengke Miao

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 3, page 577-584
  • ISSN: 2083-5892

Abstract

top
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)

How to cite

top

Shiyou Pang, et al. "On the Independence Number of Edge Chromatic Critical Graphs." Discussiones Mathematicae Graph Theory 34.3 (2014): 577-584. <http://eudml.org/doc/268142>.

@article{ShiyouPang2014,
abstract = {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)},
author = {Shiyou Pang, Lianying Miao, Wenyao Song, Zhengke Miao},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge coloring; edge-chromatic critical graphs; independence number},
language = {eng},
number = {3},
pages = {577-584},
title = {On the Independence Number of Edge Chromatic Critical Graphs},
url = {http://eudml.org/doc/268142},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Shiyou Pang
AU - Lianying Miao
AU - Wenyao Song
AU - Zhengke Miao
TI - On the Independence Number of Edge Chromatic Critical Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 3
SP - 577
EP - 584
AB - 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)
LA - eng
KW - edge coloring; edge-chromatic critical graphs; independence number
UR - http://eudml.org/doc/268142
ER -

References

top
  1. 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. [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] Zbl1033.05041
  3. [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. [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] Zbl1200.05114
  5. [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. [6] L.Y. Miao, On the independence number of edge chromatic critical graphs, Ars Combin. 98 (2011) 471-481. Zbl1249.05289
  7. [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 Zbl1024.05031
  8. [8] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian). 
  9. [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. [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] Zbl1216.05040
  11. [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] Zbl1137.05037
  12. [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] Zbl0588.05002
  13. [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] Zbl0988.05042

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.