Equitable partition of graphs into induced forests

Autor: Esperet, Louis, Lemoine, Laetitia, Maffray, Frédéric
Rok vydání: 2014
Předmět:
Zdroj: Discrete Math. 338(8) (2015), 1481-1483
Druh dokumentu: Working Paper
DOI: 10.1016/j.disc.2015.03.019
Popis: 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.
Comment: 4 pages, final version
Databáze: arXiv