Partition of Sparse Graphs into Two Forests with Bounded Degree

Matthew Yancey

paper

Partition of Sparse Graphs into Two Forests with Bounded Degree

arXiv:2403.05387

Abstract

Borodin and Kostochka proved that for $d_{2} \geq 2 d_{1} + 2$ and a graph $G$ where every subgraph $H$ satisfies $e (H) < (2 - \frac{d _{2} + 2}{( d _{1} + 2 ) ( d _{2} + 1 )}) n (H) + \frac{1}{d _{2} + 1}$ has a vertex partition $V (G) = V_{1} \cup V_{2}$ such that $G [V_{i}]$ has maximum degree at most $d_{i}$ for each $i$ . We show that under the same conditions we can additionally conclude that each $G [V_{i}]$ is a forest.