Graph Theory and Combinatorics Seminar
- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- Gregory Hall 327
- Date
- Sep 3, 2024 1:00 pm
- Speaker
- Matthew Yancey (IDA/CCS)
- Contact
- Peter Bradshaw
- pb38@illinois.edu
- Views
- 31
- Originating Calendar
- Combinatorics Research Area Calendar
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.