Journal of East China Normal University(Natural Science) >

2015 , Vol. 2015 >Issue 1: 114 - 119

DOI: https://doi.org/10.3969/j.issn.1000-5641.2015.01.013

Article

On the independence number of edge chromatic critical graphs

  • QI Lin-Ming ,
  • MIAO Lian-Ying ,
  • LI Wei-Qi
Expand
  • College of Sciences, China University of Mining and Technology, Xuzhou Jiangsu 221116, China

Received date: 2014-03-01

  Online published: 2015-03-29

Fold

Abstract

In 1968, Vizing conjectured for any edge chromatic critical graph G = (V,E) with maximum degree Δ and independence number α(G), α(G)≤|V|/2. In this paper, we proved that α(G) ≤(3Δ-3)/(5Δ-3)|V| for Δ∈{9,10} and α(G) ≤(15Δ-42)/(23Δ-42)|V| for Δ∈{11, · · · , 46}

Key words： edge coloring; critical graphs; independence number

Cite this article

QI Lin-Ming , MIAO Lian-Ying , LI Wei-Qi . On the independence number of edge chromatic critical graphs[J]. Journal of East China Normal University(Natural Science), 2015 , 2015(1) : 114 -119 . DOI: 10.3969/j.issn.1000-5641.2015.01.013

References

VIZING V G. Some unsolved problems in graph theory [J]. Uaspekhi Mat Nauk 1968, 23: 117-134; Russian Math Surveys, 1968, 23: 125-142.
LUO R, ZHAO Y. An application of Vizing and Vizing-like adjacency lemmes to Vizing's indenpence number conjecture of edge chromatic critical graphs [J]. Discrete Mathematics, 2009, 309: 2925-2929.
逄世友, 马国翼, 苗连英. 临界图独立数的上界 [J]. 徐州师范大学学报: 自然科学版, 2010, 28(1): 15-16.
MIAO L Y. On the indepence number of edge chromatic critical graphs [J]. Ars Combinatoria, 2011, 98: 471-481.
SANDERS D, ZHAO Y. Planar graphs with maximum degree seven are Class 1 [J]. Critical Graphs: J Combin Theory Ser B, 2001, 83: 201-212.
ZHANG L. Every planar graph with maximum degree 7 is of class 1 [J]. Graphs and combinatorics, 2000, 16: 467-495.
LUO R, MIAO L Y, ZHAO Y. The size of edge chromatic critical graphs with maximum degree 6 [J]. Graphs Theory, 2009, 60: 149-171.
LI S C, LI X C. Edge coloring of graphs with small maximum degree [J]. Discrete Mathematics, 2009, 309: 4843-4852.
Options
Outlines

/

〈 〉