Logo image
Se connecter
Partitioning a triangle-free planar graph into a forest and a forest of bounded degree
Acte de colloque

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

François Dross, Mickaël Montassier et Alexandre Pinlou
8th European Conference on Combinatorics, Graph Theory and Applications, Vol.Electronic Notes in Discrete Mathematics(49), pp.269-275
EuroComb: European Conference on Combinatorics, Graph Theory and Applications (Bergen, Norway, 31/08/2015–04/09/2015)
11/2015

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.

Fichiers et liens (1)

url
Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Logo image