Excluding cycles with a fixed number of chords

DOI10.1016/J.DAM.2014.08.006MaRDI QIDQ476296zbMATH OpenOpenAlexFDO

Authors Pierre Aboulker, Nicolas Bousquet

Publication date 28 November 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.1718

zbMATH Keywords

chi-boundednesschordschromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: Trotignon and Vuskovic completely characterized graphs that do not contain cycles with exactly one chord. In particular, they show that such a graph G has chromatic number at most max(3,w(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 6. And a graph G with no cycle with exactly three chords have chromatic number at most max(96,w(G)+1).

Recommendations

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• scientific article; zbMATH DE number 3904622
• Cycles in triangle-free graphs of large chromatic number
• Coloring graphs with two odd cycle lengths
• On the chromatic number of a graph with two forbidden subgraphs

Cites work

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Graph Theory and Probability
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• scientific article; zbMATH DE number 1002021 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Radius Three Trees in Graphs with Large Chromatic Number
• Radius two trees specify χ‐bounded classes
• The strong perfect graph theorem
• Triangle-free intersection graphs of line segments with large chromatic number

Cited in

(6)

• Requiring chords in cycles
• Excluding clocks
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Triangle‐free graphs with large chromatic number and no induced wheel
• The chromatic number of heptagraphs
• Chi-boundedness of graphs containing no cycles with k chords

This page was built for publication: Excluding cycles with a fixed number of chords

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476296)