Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777359 | European Journal of Combinatorics | 2017 | 14 Pages |
Abstract
An (F,Fd)-partition of a graph is a vertex-partition into two sets F and Fd such that the graph induced by F is a forest and the one induced by Fd is a forest with maximum degree at most d. We prove that every triangle-free planar graph admits an (F,F5)-partition. Moreover we show that if for some integer d there exists a triangle-free planar graph that does not admit an (F,Fd)-partition, then it is an NP-complete problem to decide whether a triangle-free planar graph admits such a partition.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
François Dross, Mickael Montassier, Alexandre Pinlou,