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 条
[41]   On the chromatic number of Toeplitz graphs [J].
Nicoloso, Sara ;
Pietropaoli, Ugo .
DISCRETE APPLIED MATHEMATICS, 2014, 164 :286-296
[42]   MONOTONE CHROMATIC NUMBER OF GRAPHS [J].
Saleh, Anwar ;
Muthana, Najat ;
Al-Shammakh, Wafa ;
Alashwali, Hanaa .
INTERNATIONAL JOURNAL OF ANALYSIS AND APPLICATIONS, 2020, 18 (06) :1108-1122
[43]   On the harmonious chromatic number of graphs [J].
Araujo-Pardo, Gabriela ;
Montellano-Ballesteros, Juan Jose ;
Olsen, Mika ;
Rubio-Montiel, Christian .
BOLETIN DE LA SOCIEDAD MATEMATICA MEXICANA, 2024, 30 (02)
[44]   Isolation of Regular Graphs and k-Chromatic Graphs [J].
Borg, Peter .
MEDITERRANEAN JOURNAL OF MATHEMATICS, 2024, 21 (05)
[45]   Chromatic number and subtrees of graphs [J].
Xu, Baogang ;
Zhang, Yingli .
FRONTIERS OF MATHEMATICS IN CHINA, 2017, 12 (02) :441-457
[46]   On Indicated Chromatic Number of Graphs [J].
Raj, S. Francis ;
Raj, R. Pandiya ;
Patil, H. P. .
GRAPHS AND COMBINATORICS, 2017, 33 (01) :203-219
[47]   On the chromatic number of tree graphs [J].
Estivill-Castro, V ;
Noy, M ;
Urrutia, J .
DISCRETE MATHEMATICS, 2000, 223 (1-3) :363-366
[48]   CHROMATIC NUMBER OF SKEW GRAPHS [J].
PAHLINGS, H .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 25 (03) :303-306
[49]   The chromatic number of oriented graphs [J].
Sopena, E .
JOURNAL OF GRAPH THEORY, 1997, 25 (03) :191-205
[50]   COMPLEMENTARY GRAPHS AND THE CHROMATIC NUMBER [J].
Starr, Colin L. ;
Turner, Galen E., III .
MISSOURI JOURNAL OF MATHEMATICAL SCIENCES, 2008, 20 (01) :19-26
12345