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

Series: 
Combinatorics Seminar
Friday, November 4, 2011 - 15:05
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
University of Illinois
Organizer: 
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.