On the independence number of edge chromatic critical graphs

QI Lin-Ming; MIAO Lian-Ying; LI Wei-Qi

doi:10.3969/j.issn.1000-5641.2015.01.013

Issue 1

Mar. 2015

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2015 > (1): 114-119

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 Sciences), 2015, (1): 114-119. doi: 10.3969/j.issn.1000-5641.2015.01.013

Citation:

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 Sciences), 2015, (1): 114-119. doi: 10.3969/j.issn.1000-5641.2015.01.013

Citation:

PDF( 235 KB)

On the independence number of edge chromatic critical graphs

doi: 10.3969/j.issn.1000-5641.2015.01.013

1.
College of Sciences, China University of Mining and Technology, Xuzhou Jiangsu 221116, China

Received Date: 2014-03-01
Publish Date: 2015-01-25

Abstract

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}
- edge coloring,
- critical graphs,
- independence number

FullText(HTML)

References(1)

References

[1]

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.

Relative Articles

Supplements(0)

Cited By

Proportional views