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
Communication Dans Un Congrès Année : 2015

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

François Dross
Mickaël Montassier

Résumé

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.

Dates et versions

lirmm-01233461 , version 1 (25-11-2015)

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. EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Aug 2015, Bergen, Norway. pp.269-275, ⟨10.1016/j.endm.2015.06.037⟩. ⟨lirmm-01233461⟩
123 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More