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 条
  • [1] An application of Vizing and Vizing-like adjacency lemmas to Vizing's Independence Number Conjecture of edge chromatic critical graphs
    Luo, Rong
    Zhao, Yue
    DISCRETE MATHEMATICS, 2009, 309 (09) : 2925 - 2929
  • [2] ON THE INDEPENDENCE NUMBER OF EDGE CHROMATIC CRITICAL GRAPHS
    Pang, Shiyou
    Miao, Lianying
    Song, Wenyao
    Miao, Zhengke
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2014, 34 (03) : 577 - 584
  • [3] On the Independence Number of Edge Chromatic Critical Graphs
    Miao Lianying
    ARS COMBINATORIA, 2011, 98 : 471 - 481
  • [4] A New Upper Bound for the Independence Number of Edge Chromatic Critical Graphs
    Luo, Rong
    Zhao, Yue
    JOURNAL OF GRAPH THEORY, 2011, 68 (03) : 202 - 212
  • [5] Vizing's adjacency lemma on edge chromatic critical signed graphs and its applications
    Cao, Yan
    Luo, Rong
    Miao, Zhengke
    Zhao, Yue
    DISCRETE APPLIED MATHEMATICS, 2023, 329 : 96 - 105
  • [6] The Independence Number of an Edge-Chromatic Critical Graph
    Woodall, Douglas R.
    JOURNAL OF GRAPH THEORY, 2011, 66 (02) : 98 - 103
  • [7] Reducing Vizing's 2-Factor Conjecture to Meredith Extension of Critical Graphs
    Chen, Xiaodong
    Ji, Qing
    Liu, Mingda
    GRAPHS AND COMBINATORICS, 2020, 36 (05) : 1585 - 1591
  • [8] On the size of edge chromatic critical graphs
    Sanders, DP
    Zhao, Y
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (02) : 408 - 412
  • [9] Reducing Vizing’s 2-Factor Conjecture to Meredith Extension of Critical Graphs
    Xiaodong Chen
    Qing Ji
    Mingda Liu
    Graphs and Combinatorics, 2020, 36 : 1585 - 1591
  • [10] A note on the size of edge-chromatic 4-critical graphs
    Cheng, Jian
    Lorenzen, Kate J.
    Luo, Rong
    Thompson, Joshua C.
    DISCRETE MATHEMATICS, 2016, 339 (10) : 2393 - 2398
12345