pith. sign in

arxiv: 1410.0861 · v3 · pith:JSNF72LTnew · submitted 2014-10-03 · 🧮 math.CO

Equitable partition of graphs into induced forests

classification 🧮 math.CO
keywords forestsgraphinducedpartitionequitableequitablypartitionedacyclic
0
0 comments X
read the original abstract

An equitable partition of a graph $G$ is a partition of the vertex-set of $G$ such that the sizes of any two parts differ by at most one. We show that every graph with an acyclic coloring with at most $k$ colors can be equitably partitioned into $k-1$ induced forests. We also prove that for any integers $d\ge 1$ and $k\ge 3^{d-1}$, any $d$-degenerate graph can be equitably partitioned into $k$ induced forests. Each of these results implies the existence of a constant $c$ such that for any $k \ge c$, any planar graph has an equitable partition into $k$ induced forests. This was conjectured by Wu, Zhang, and Li in 2013.

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.