Combinatorial Optimization Reading Group - Ben Moore

Title: On the Strong Nine Dragon Tree Conjecture

Abstract:

Nash-Williams forest covering theorem says that a graph decomposes into $k$ forests if and only if it has fractional arboricity at most $k$. In 2012 Mickeal Montassier, Patrice Ossona de Mendez, Andre Raspaud, and Xuding Zhu  proposed a significant strengthening of Nash-Williams Theorem, called the Strong Nine Dragon Tree Conjecture. The Strong Nine Dragon Tree Conjecture asserts that if a graph $G$ has fractional arboricity at most $k + d/(k+d+1)$, then $G$ decomposes into $k+1$ forests so that one of the forests has every connected component containing at most $d$ edges.   Montassier et al. showed the conjecture was true when $k=1$ and $d=1$. In 2013, Seog-jin Kim, Alexandr Kostochka, Doug West, Hehui Wu, and Xuding Zhu proved the conjecture when $k =1$, $d=2$. In 2017, Daqing Yang generalized this to any $k$ and $d=1$.  Last year, I proved the conjecture when $d \leq k+1$, and showed that if you change $d$ edges to a function of $k$ and $d$, then the conjecture is true.  Recently, I believe that is is possible to prove the $k=1$ and $d=3,4$ case, and I will present work towards this.