On graphs with no induced subdivision of K4

Benjamin Lévêque 1 Frédéric Maffray 2 Nicolas Trotignon 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 G-SCOP_OC - OC
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : We prove a decomposition theorem for graphs that do not contain a subdivision of K 4 as an induced subgraph where K 4 is the complete graph on four vertices. We obtain also a structure theorem for the class C of graphs that contain neither a subdivision of K 4 nor a wheel as an induced subgraph, where a wheel is a cycle on at least four vertices together with a vertex that has at least three neighbors on the cycle. Our structure theorem is used to prove that every graph in C is 3-colorable and entails a polynomial-time recognition algorithm for membership in C . As an intermediate result, we prove a structure theorem for the graphs whose cycles are all chordless.
Type de document :
Article dans une revue
Journal of Combinatorial Theory, Series B, Elsevier, 2012, 102, pp.924-947. 〈10.1016/j.jctb.2012.04.005〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736503
Contributeur : Benjamin Lévêque <>
Soumis le : vendredi 28 septembre 2012 - 12:35:55
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Benjamin Lévêque, Frédéric Maffray, Nicolas Trotignon. On graphs with no induced subdivision of K4. Journal of Combinatorial Theory, Series B, Elsevier, 2012, 102, pp.924-947. 〈10.1016/j.jctb.2012.04.005〉. 〈lirmm-00736503〉

Partager

Métriques

Consultations de la notice

194