Excluding cycles with a fixed number of chords

DOI10.1016/J.DAM.2014.08.006zbMATH Open1303.05093arXiv1304.1718OpenAlexW2098531449MaRDI QIDQ476296FDOQ476296

Authors: Pierre Aboulker, Nicolas Bousquet 

Publication date: 28 November 2014

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

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).

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

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

zbMATH Keywords

chordschi-boundednesschromatic number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Requiring chords in cycles
• 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

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)