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 条
[31]   Uniquely colorable graphs with equal chromatic and game chromatic numbers [J].
Matsumoto, Naoki .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (03)
[32]   The difference between game chromatic number and chromatic number of graphs [J].
Matsumoto, Naoki .
INFORMATION PROCESSING LETTERS, 2019, 151
[33]   Graphs with tiny vector chromatic numbers and huge chromatic numbers [J].
Feige, U ;
Langberg, M ;
Schechtman, G .
SIAM JOURNAL ON COMPUTING, 2004, 33 (06) :1338-1368
[34]   Vertex-critical graphs far from edge-criticality [J].
Martinsson, Anders ;
Steiner, Raphael .
COMBINATORICS PROBABILITY AND COMPUTING, 2025, 34 (01) :151-157
[35]   CIRCULAR CHROMATIC NUMBER AND MYCIELSKI GRAPHS [J].
刘红美 .
Acta Mathematica Scientia, 2006, (02) :314-320
[36]   The Chromatic Number of Joins of Signed Graphs [J].
Mattern, Amelia R. W. .
GRAPHS AND COMBINATORICS, 2021, 37 (06) :2723-2735
[37]   THE CHROMATIC NUMBER OF RANDOM INTERSECTION GRAPHS [J].
Rybarczyk, Katarzyna .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2017, 37 (02) :465-476
[38]   On Chromatic Number of Colored Mixed Graphs [J].
Das, Sandip ;
Nandi, Soumen ;
Sen, Sagnik .
ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, 2017, 10156 :130-140
[39]   Orientations of graphs with uncountable chromatic number [J].
Soukup, Daniel T. .
JOURNAL OF GRAPH THEORY, 2018, 88 (04) :606-630
[40]   Chromatic numbers of integer distance graphs [J].
Kemnitz, A ;
Marangio, M .
DISCRETE MATHEMATICS, 2001, 233 (1-3) :239-246
12345