Excluding cycles with a fixed number of chords - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Discrete Applied Mathematics Année : 2015

Excluding cycles with a fixed number of chords

Résumé

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).
Fichier principal
Vignette du fichier
1304.1718.pdf (274.33 Ko) Télécharger le fichier
Origine Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

lirmm-01350552 , version 1 (26-01-2024)

Identifiants

Citer

Pierre Aboulker, Nicolas Bousquet. Excluding cycles with a fixed number of chords. Discrete Applied Mathematics, 2015, 180, pp.11-24. ⟨10.1016/j.dam.2014.08.006⟩. ⟨lirmm-01350552⟩
150 Consultations
6 Téléchargements

Altmetric

Partager

More