pith. sign in

arxiv: 1601.01523 · v1 · pith:OSITF3MEnew · submitted 2016-01-07 · 💻 cs.DM · math.CO

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

classification 💻 cs.DM math.CO
keywords graphforestpartitionplanartriangle-freeadmitsdegreeinduced
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.