Article ID Journal Published Year Pages File Type
418643 Discrete Applied Mathematics 2015 14 Pages PDF
Abstract

Trotignon and Vušković completely characterized graphs that do not contain cycles with exactly one chord. In particular, they show that such a graph GG has chromatic number at most max(3,ω(G))max(3,ω(G)). We generalize this result to the class of graphs that do not contain cycles with exactly two chords and the class of graphs that do not contain cycles with exactly three chords.More precisely we prove that graphs with no cycle with exactly two chords have chromatic number at most 66. And a graph GG with no cycle with exactly three chords has chromatic number at most max(96,ω(G)+1)max(96,ω(G)+1).

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,