2013/04/05 by Pierre Bousquet, Pierre Aboulker 'and' Nicolas Bousquet, Bousquet, Pierre Aboulker 'and' Nicolas
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1304.1718
30 pages, 7 figures
arxiv created 2013/04/05 · openalex publication_date 2013/04/05 · arxiv updated 2013/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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).