A New Upper Bound for the Independence Number of Edge Chromatic Critical Graphs

被引：4

作者：

Luo, Rong ^{[1
]}

Zhao, Yue ^{[2
]}

机构：

[1] Middle Tennessee State Univ, Dept Math Sci, Murfreesboro, TN 37132 USA

[2] Univ Cent Florida, Dept Math, Orlando, FL 32816 USA

来源：

JOURNAL OF GRAPH THEORY | 2011年 / 68卷 / 03期

关键词：

edge coloring; independence number; critical graphs; CONJECTURE;

D O I：

10.1002/jgt.20552

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1968, Vizing conjectured that if G is a Delta-critical graph with n vertices, then alpha(G)<= n/2, where alpha(G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that alpha(G)<(((5 Delta-6)n)/(8 Delta-6))<5n/8 if Delta >= 6. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68: 202-212, 2011

引用

页码：202 / 212

页数：11

共 12 条

[1] Bounds for the independence number of critical graphs [J].

Brinkmann, G ;

Choudum, SA ;

Grünewald, S ;

Steffen, E .

BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2000, 32 :137-140

[2]

FAVRHOLDT LM, 2006, 20 IMADA U SO DENM

[3] Independent sets and 2-factors in edge-chromatic-critical graphs [J].

Grünewald, S ;

Steffen, E .

JOURNAL OF GRAPH THEORY, 2004, 45 (02) :113-118

[4]

Jensen T., 1995, Graph Coloring Problems, P115

[5]

LUO R, FINDING DELTA SIGMA, DOI DOI 10.1002/JGT.20548

[6] A note on Vizing's independence number conjecture of edge chromatic critical graphs [J].

Luo, Rong ;

Zhao, Yue .

DISCRETE MATHEMATICS, 2006, 306 (15) :1788-1790

[7] An application of Vizing and Vizing-like adjacency lemmas to Vizing's Independence Number Conjecture of edge chromatic critical graphs [J].

Luo, Rong ;

Zhao, Yue .

DISCRETE MATHEMATICS, 2009, 309 (09) :2925-2929

[8] The Size of Edge Chromatic Critical Graphs with Maximum Degree 6 [J].

Luo, Rong ;

Miao, Lianying ;

Zhao, Yue .

JOURNAL OF GRAPH THEORY, 2009, 60 (02) :149-171

[9] Planar graphs of maximum degree seven are class I [J].

Sanders, DP ;

Zhao, Y .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 83 (02) :201-212

[10]

Vizing V.G., 1965, Cybernetics, V1, P32

← 1 2 →