Partitioning a triangle-free planar graph into a forest and a forest of bounded degree - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue European Journal of Combinatorics Année : 2017

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

François Dross
Mickaël Montassier

Résumé

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.

Dates et versions

lirmm-01430784 , version 1 (10-01-2017)

Identifiants

Citer

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, 2017, 66, pp.81-94. ⟨10.1016/j.ejc.2017.06.014⟩. ⟨lirmm-01430784⟩
106 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More