Partitioning a triangle-free planar graph into a forest and a forest of bounded degree

François Dross 1 Mickaël Montassier 1 Alexandre Pinlou 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We prove that every triangle-free planar graph can have its set of vertices partitioned into two sets, one inducing a forest and the other a forest with maximum degree at most 5. We also show that if for some d, there is a triangle-free planar graph that cannot be partitioned into two sets, one inducing a forest and the other a forest with maximum degree at most d, then it is an NP-complete problem to decide if a triangle-free planar graph admits such a partition.
Type de document :
Communication dans un congrès
EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Aug 2015, Bergen, Norway. 8th European Conference on Combinatorics, Graph Theory and Applications, Electronic Notes in Discrete Mathematics (49), pp.269-275, 2015, 〈https://eurocomb2015.w.uib.no〉. 〈10.1016/j.endm.2015.06.037〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233461
Contributeur : Alexandre Pinlou <>
Soumis le : mercredi 25 novembre 2015 - 11:28:57
Dernière modification le : mercredi 14 février 2018 - 22:15:42

Lien texte intégral

Identifiants

Collections

Citation

François Dross, Mickaël Montassier, Alexandre Pinlou. Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Aug 2015, Bergen, Norway. 8th European Conference on Combinatorics, Graph Theory and Applications, Electronic Notes in Discrete Mathematics (49), pp.269-275, 2015, 〈https://eurocomb2015.w.uib.no〉. 〈10.1016/j.endm.2015.06.037〉. 〈lirmm-01233461〉

Partager

Métriques

Consultations de la notice

76