Excluding cycles with a fixed number of chords

Pierre Aboulker 1 Nicolas Bousquet 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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).
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2015, 180, pp.11-24. 〈10.1016/j.dam.2014.08.006〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01350552
Contributeur : Isabelle Gouat <>
Soumis le : dimanche 31 juillet 2016 - 06:51:02
Dernière modification le : jeudi 31 mai 2018 - 14:54:03

Lien texte intégral

Identifiants

Collections

Citation

Pierre Aboulker, Nicolas Bousquet. Excluding cycles with a fixed number of chords. Discrete Applied Mathematics, Elsevier, 2015, 180, pp.11-24. 〈10.1016/j.dam.2014.08.006〉. 〈lirmm-01350552〉

Partager

Métriques

Consultations de la notice

108