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 条

[11] Normalized Laplacian eigenvalues with chromatic number and independence number of graphs
Sun, Shaowei
Das, Kinkar Ch
LINEAR & MULTILINEAR ALGEBRA, 2020, 68 (01) : 63 - 80
[12] Ohba's conjecture is true for graphs with independence number at most three
Shen, Yufa
He, Wenjie
Zheng, Guoping
Li, Yanpo
APPLIED MATHEMATICS LETTERS, 2009, 22 (06) : 938 - 942
[13] Hamiltonicity of edge chromatic critical graphs
Chen, Guantao
Chen, Xiaodong
Zhao, Yue
DISCRETE MATHEMATICS, 2017, 340 (12) : 3011 - 3015
[14] Graphs that are Critical for the Packing Chromatic Number
Bresar, Bostjan
Ferme, Jasmina
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (02) : 569 - 589
[15] Remarks on planar edge-chromatic critical graphs
Jin, Ligang
Kang, Yingli
Steffen, Eckhard
DISCRETE APPLIED MATHEMATICS, 2016, 200 : 200 - 202
[16] DISTANCE LAPLACIAN EIGENVALUES OF GRAPHS, AND CHROMATIC AND INDEPENDENCE NUMBER
Pirzada, Shariefuddin
Khan, Saleem
REVISTA DE LA UNION MATEMATICA ARGENTINA, 2024, 67 (01): : 145 - 159
[17] Independence Number and Maximal Chromatic Polynomials of Connected Graphs
Long, Shude
Cai, Junliang
GRAPHS AND COMBINATORICS, 2024, 40 (05)
[18] Acyclic Edge Chromatic Number of Outerplanar Graphs
Hou, Jian-Feng
Wu, Jian-Liang
Liu, Gui-Zhen
Liu, Bin
JOURNAL OF GRAPH THEORY, 2010, 64 (01) : 22 - 36
[19] On the average degree of edge chromatic critical graphs
Cao, Yan
Chen, Guantao
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2021, 147 : 299 - 338
[20] Edge Chromatic 5-Critical Graphs of Order 15
Kayathri, K.
Devi, J. Sakila
GRAPH ALGORITHMS, HIGH PERFORMANCE IMPLEMENTATIONS AND ITS APPLICATIONS (ICGHIA 2014), 2015, 47 : 332 - 336

← 1 2 3 4 5 →