A note on Vizing's independence number conjecture of edge chromatic critical graphs

被引：14

作者：

Luo, Rong ^{[1
]}

Zhao, Yue

机构：

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

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

来源：

DISCRETE MATHEMATICS | 2006年 / 306卷 / 15期

关键词：

independence number; critical graph; edge coloring; class one; class two;

D O I：

10.1016/j.disc.2006.03.040

中图分类号：

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 note, we verify this conjecture for n <= 2 Delta. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：1788 / 1790

页数：3

共 49 条

[41] PRECISE UPPER BOUND FOR THE STRONG EDGE CHROMATIC NUMBER OF SPARSE PLANAR GRAPHS
Borodin, Oleg V.
Ivanova, Anna O.
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (04) : 759 - 770
[42] INDEPENDENCE NUMBER, CONNECTIVITY AND ALL FRACTIONAL (a, b, k)-CRITICAL GRAPHS
Yuan, Yuan
Hao, Rong-Xia
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (01) : 183 - 190
[43] Independence number and connectivity of maximal connected domination vertex critical graphs
Almalki, Norah
Kaemawicharnurat, Pawaton
COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2023, 9 (02) : 185 - 196
[44] Independence number and minimum degree for path-factor critical uniform graphs
Liu, Hongxia
Pan, Xiaogang
DISCRETE APPLIED MATHEMATICS, 2024, 359 : 153 - 158
[45] Independence Number and Minimum Degree for the Existence of (g, f, n)-Critical Graphs
Zhou, Sizhong
Pan, Quanru
Xu, Yang
ANALELE STIINTIFICE ALE UNIVERSITATII OVIDIUS CONSTANTA-SERIA MATEMATICA, 2011, 19 (01): : 373 - 381
[46] An upper bound on the number of edges of edge-coloring critical graphs with high maximum degree
Miao, LY
Pang, SY
Wu, JL
DISCRETE MATHEMATICS, 2003, 271 (1-3) : 321 - 325
[47] Independence number and minimum degree for fractional ID-k-factor-critical graphs
Zhou, Sizhong
Xu, Lan
Sun, Zhiren
AEQUATIONES MATHEMATICAE, 2012, 84 (1-2) : 71 - 76
[48] Independence number and minimum degree for fractional ID-k-factor-critical graphs
Sizhong Zhou
Lan Xu
Zhiren Sun
Aequationes mathematicae, 2012, 84 : 71 - 76
[49] Proof of the Caccetta-Haggkvist conjecture for oriented graphs with positive minimum out-degree and of independence number two
Lichiardopol, Nicolas
DISCRETE MATHEMATICS, 2013, 313 (14) : 1540 - 1542

← 1 2 3 4 5 →