Speaker: Alexandr Kostochka (UIUC)
Title: Partition of Sparse Multigraphs into a Forest and a Forest with Restrictions
Abstract: Call a loopless multigraph $H$ {\em $(a, b)$-sparse} if for every $A \subseteq V (H)$ with $|A|>1$, the induced subgraph $H[A]$ has at most $a|A| + b$ edges.
For a given $D$ we study for which pairs $(a, b)$ every $(a, b)$-sparse loopless multigraph $G$ admits a vertex partition $(V_1,V_2)$ of $V(G)$ such that $G[V_1]$ and $G[V_2]$ are forests, and either (i) the maximum degree of $G[V1]$ is at most $D$ or (ii) every component of $G[V1]$ has at most $D$ edges. We find exact bounds on $a$ and $b$ for both types of problems (i) and (ii). We also consider problems of type (i) in the class of simple graphs and find exact bounds for all $D\geq 2$.
This is joint work with Ilkyoo Choi and Matthew Yancey.