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 : An $({\cal F},{\cal F}_d)$-partition of a graph is a vertex-partition into two sets $F$ and $F_d$ such that the graph induced by $F$ is a forest and the one induced by $F_d$ is a forest with maximum degree at most $d$. We prove that every triangle-free planar graph admits an $({\cal F},{\cal F}_5)$-partition. Moreover we show that if for some integer $d$ there exists a triangle-free planar graph that does not admit an $({\cal F},{\cal F}_d)$-partition, then it is an NP-complete problem to decide whether a triangle-free planar graph admits such a partition.
Type de document :
Article dans une revue
European Journal of Combinatorics, Elsevier, 2017, 66, pp.81-94
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01430784
Contributeur : Mickael Montassier <>
Soumis le : mardi 10 janvier 2017 - 11:40:37
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

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. European Journal of Combinatorics, Elsevier, 2017, 66, pp.81-94. 〈lirmm-01430784〉

Partager

Métriques

Consultations de la notice

93