Cycle lengths and chromatic number of graphs

被引：17

作者：

Mihók, P

Schiermeyer, I

机构：

[1] Tech Univ, Fac Econ, Kosice 04001, Slovakia

[2] Slovak Acad Sci, Math Inst, Kosice 04001, Slovakia

[3] Tech Univ Bergakad Freiberg, Inst Diskrete Math & Algebra, D-09596 Freiberg, Germany

来源：

DISCRETE MATHEMATICS | 2004年 / 286卷 / 1-2期

关键词：

chromatic number; cycle length; k-degenerate graph;

D O I：

10.1016/j.disc.2003.11.055

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For a simple finite graph G let C-o(G) and C-e(G) denote the set of odd cycle lengths and even cycle lengths in a graph G, respectively. We will show that the chromatic number chi(G) of G satisfies: chi(G) less than or equal to min {2r + 2,2s + 3} less than or equal to r + s + 2, if \Co(G)\ = r and \Ce(G)\ = s. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：147 / 149

页数：3

共 50 条

[31] On the injective chromatic number of graphs
Hahn, G
Kratochvíl, J
Sirán, J
Sotteau, D
DISCRETE MATHEMATICS, 2002, 256 (1-2) : 179 - 192
[32] ON THE DYNAMIC CHROMATIC NUMBER OF GRAPHS
Akbari, S.
Ghanbari, M.
Jahanbekam, S.
COMBINATORICS AND GRAPHS, 2010, 531 : 11 - +
[33] ON THE CHROMATIC NUMBER OF THE PRODUCT OF GRAPHS
DUFFUS, D
SANDS, B
WOODROW, RE
JOURNAL OF GRAPH THEORY, 1985, 9 (04) : 487 - 495
[34] On incompactness for chromatic number of graphs
Saharon Shelah
Acta Mathematica Hungarica, 2013, 139 : 363 - 371
[35] THE CHROMATIC NUMBER OF RANDOM GRAPHS
BOLLOBAS, B
COMBINATORICA, 1988, 8 (01) : 49 - 55
[36] On the chromatic number of circulant graphs
Barajas, Javier
Serra, Oriol
DISCRETE MATHEMATICS, 2009, 309 (18) : 5687 - 5696
[37] On Group Chromatic Number of Graphs
Hong-Jian Lai
Xiangwen Li
Graphs and Combinatorics, 2005, 21 : 469 - 474
[38] On the adaptable chromatic number of graphs
Hell, Pavol
Zhu, Xuding
EUROPEAN JOURNAL OF COMBINATORICS, 2008, 29 (04) : 912 - 921
[39] On the chromatic number of random graphs
Coja-Oghlan, Amin
Panagiotou, Konstantinos
Steger, Angelika
AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS, 2007, 4596 : 777 - +
[40] The edge-distinguishing chromatic number of spider graphs with three legs or bounded leg lengths
Fickes, Grant
Wong, Tony W. H.
Journal of Combinatorial Mathematics and Combinatorial Computing, 2020, 113 : 165 - 181

← 1 2 3 4 5 →