REGULAR GRAPHS WITH PRESCRIBED CHROMATIC NUMBER

被引：1
作者：
CACCETTA, L [1 ]
PULLMAN, NJ [1 ]
机构：
[1] QUEENS UNIV,KINGSTON K7L 3N6,ONTARIO,CANADA
来源：
JOURNAL OF GRAPH THEORY | 1990年 / 14卷 / 01期
关键词：
D O I：
10.1002/jgt.3190140107
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We determine the minimum number of edges in a regular connected graph on n vertices, containing a complete subgraph of order k ≤ n/2. This enables us to confirm and strengthen a conjecture of P. Erdös on the existence of regular graphs with prescribed chromatic number. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company
引用
收藏
页码：65 / 71
页数：7
相关论文
共 50 条
[21]   The b-chromatic number of regular graphs via the edge-connectivity [J].
Shaebani, Saeed .
DISCRETE MATHEMATICS, 2013, 313 (22) :2663-2666
[22]   Random regular graphs of non-constant degree: Independence and chromatic number [J].
Cooper, C ;
Frieze, A ;
Reed, B ;
Riordan, O .
COMBINATORICS PROBABILITY & COMPUTING, 2002, 11 (04) :323-341
[23]   Random regular graphs of non-constant degree: Concentration of the chromatic number [J].
Ben-Shimon, Sonny ;
Krivelevich, Michael .
DISCRETE MATHEMATICS, 2009, 309 (12) :4149-4161
[24]   On the b-chromatic number of regular graphs without 4-cycle [J].
Shaebani, Saeed .
DISCRETE APPLIED MATHEMATICS, 2012, 160 (10-11) :1610-1614
[25]   Chromatic number of regular walls [J].
Vietri, A .
ARS COMBINATORIA, 2005, 76 :97-111
[26]   CHROMATIC NUMBER OF REGULAR MATROIDS [J].
LINDSTROM, B .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 24 (03) :367-369
[27]   On minimal triangle-free graphs with prescribed k-defective chromatic number [J].
Achuthan, Nirmala ;
Achuthan, N. R. ;
Simanihuruk, M. .
DISCRETE MATHEMATICS, 2011, 311 (13) :1119-1127
[28]   Graphs whose circular chromatic number equals the chromatic number [J].
Zhu, XD .
COMBINATORICA, 1999, 19 (01) :139-149
[29]   The difference between game chromatic number and chromatic number of graphs [J].
Matsumoto, Naoki .
INFORMATION PROCESSING LETTERS, 2019, 151
[30]   Graphs Whose Circular Chromatic Number Equals the Chromatic Number [J].
Xuding Zhu .
Combinatorica, 1999, 19 :139-149
12345