Speaker: Matthew Yancey (IDA/CCS)
Title: Partitioning sparse graphs in bounded degree forests
Abstract: A graph $G$ is $(a, b)$-sparse if every subgraph $H$ satisfies $e(H) \leq a n(H) - b$, which is a condition that has shown up in electrical circuit design, pebble games, and matroids. In 2014 Borodin and Kostochka gave the optimal sparsity condition for a graph to have a vertex partition $V = V_1 \cup V_2$ such that each $V_i$ induces a graph with maximum degree at most $d_i$, when $d_2 \geq 2d_1 + 2$. We show that under the same conditions it also holds that each $G[V_i]$ is a forest.