Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree

Combinatorics Seminar
Friday, November 4, 2011 - 15:05
1 hour (actually 50 minutes)
Skiles 005
University of Illinois
Say that a graph with maximum degree at most $d$ is {\it $d$-bounded}.  For$d>k$, we prove a sharp sparseness condition for decomposition into $k$ forestsand a $d$-bounded graph.  The condition holds for every graph with fractionalarboricity at most $k+\FR d{k+d+1}$.  For $k=1$, it also implies that everygraph with maximum average degree less than $2+\FR{2d}{d+2}$ decomposes intoone forest and a $d$-bounded graph, which contains several earlier results onplanar graphs.