Cycle lengths and chromatic number of graphs
type: Item
instance of: scholarly article
title: Cycle lengths and chromatic number of graphs
zbMATH Open document ID: 1055.05060
author: Peter Mihók
author: Ingo Schiermeyer
published in: Discrete Mathematics
publication date: 2004-10-01T00:00:00Z
review text: Let \(r(G)\) and \(s(G)\) be the number of odd and even cycle lengths in a graph \(G,\) respectively. It is shown that for each graph \(G\) its chromatic number satisfies \(\chi (G)\leq \min \{2r(G)+2,2s(G)+3\}.\)
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 2105621
zbMATH Keywords: graph
zbMATH Keywords: chromatic number
zbMATH Keywords: cycle length
reviewed by: Peter Horák
MaRDI profile type: Publication
full work available at URL: j.disc.2003.11.055
OpenAlex ID: W2122560436
cites work: Q5422499
cites work: Q3491635
cites work: Graphs with \(k\) odd cycle lengths
cites work: Q3433915
cites work: Colouring Graphs with Prescribed Induced Cycle Lengths
DOI: 10.1016/J.DISC.2003.11.055
Recommended article: Cycle length parities and the chromatic number
Recommended article: The number of shortest cycles and the chromatic uniqueness of a graph
Recommended article: Cycles and new bounds for the chromatic number
Recommended article: Cycle lengths and minimum degree of graphs
Recommended article: On the chromatic number of circulant graphs
Recommended article: Cycles of given lengths in hypergraphs
Recommended article: Induced cycles and chromatic number
Recommended article: Cycles in triangle-free graphs of large chromatic number
Recommended article: Q5488337
Recommended article: The chromatic polynomial for cycle graphs
description: scientific article; zbMATH DE number 2105621