On the size of edge chromatic critical graphs

被引：14
|
作者：
Sanders, DP [1 ]
Zhao, Y [1 ]
机构：
[1] Univ Cent Florida, Dept Math, Orlando, FL 32816 USA
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2002年 / 86卷 / 02期
基金：
美国国家科学基金会;
关键词：
chromatic number; class one; class two;
D O I：
10.1006/jctb.2002.2135
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this paper, by applying the discharging method, we prove that if G = (V, E) is a Delta-critical graph, then \E\ greater than or equal to 1/4\V\(Delta + root2Delta-1). (C) 2002 Elsevier Science (USA).
引用
收藏
页码：408 / 412
页数：5
相关论文
共 50 条
  • [1] New lower bounds for the size of edge chromatic critical graphs
    Zhao, Y
    JOURNAL OF GRAPH THEORY, 2004, 46 (02) : 81 - 92
  • [2] The Size of Edge Chromatic Critical Graphs with Maximum Degree 6
    Luo, Rong
    Miao, Lianying
    Zhao, Yue
    JOURNAL OF GRAPH THEORY, 2009, 60 (02) : 149 - 171
  • [3] 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
  • [4] A Class of Edge Critical 4-Chromatic Graphs
    Guantao Chen
    Paul Erdős
    András Gyárfás
    R. H. Schelp
    Graphs and Combinatorics, 1997, 13 : 139 - 146
  • [5] A class of edge critical 4-chromatic graphs
    Chen, GT
    Erdos, P
    Gyarfas, A
    Schelp, RH
    GRAPHS AND COMBINATORICS, 1997, 13 (02) : 139 - 146
  • [6] A note on Vizing's independence number conjecture of edge chromatic critical graphs
    Luo, Rong
    Zhao, Yue
    DISCRETE MATHEMATICS, 2006, 306 (15) : 1788 - 1790
  • [7] 4-chromatic edge critical Grotzsch-Sachs graphs
    Dobrynin, A. A.
    Mel'nikov, L. S.
    DISCRETE MATHEMATICS, 2009, 309 (08) : 2564 - 2566
  • [8] On the Chromatic Edge Stability Number of Graphs
    Arnfried Kemnitz
    Massimiliano Marangio
    Nazanin Movarraei
    Graphs and Combinatorics, 2018, 34 : 1539 - 1551
  • [9] On the Chromatic Edge Stability Number of Graphs
    Kemnitz, Arnfried
    Marangio, Massimiliano
    Movarraei, Nazanin
    GRAPHS AND COMBINATORICS, 2018, 34 (06) : 1539 - 1551
  • [10] Edge-critical subgraphs of Schrijver graphs
    Kaiser, Tomas
    Stehlik, Matej
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 144 : 191 - 196
12345