Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. (December 2017)

• Record Type: Journal Article
• Authors: Dross, François; Montassier, Mickael; Pinlou, Alexandre
• Is Part Of: European journal of combinatorics. Volume 66(2017)
• Page Start: 81
• Page End: 94
• Publication Date: 2017-12
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.06.014
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: An ( F, 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 ( F, F 5 ) -partition. Moreover we show that if for some integer d there exists a triangle-free planar graph that does not admit an ( F, F d ) -partition, then it is an NP-complete problem to decide whether a triangle-free planar graph admits such a partition.