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 |
Externí odkaz: |