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