Some recent Nine Dragon Tree style results

Benjamin Moore


October 21, 2021, 12:20 in S6


An old result of Nash-Williams tells us exactly when you can colour the edges of a graph using k colours, such that each colour induces a forest (we call such a colouring a decomposition). It is precisely when for every subgraph H of a graph G, the number of edges of H is bounded by k(|V(H)|-1), and this bound cannot be improved further. In 2012, Montassier, Ossona de Mendez, Raspaud, and Zhu posed the Strong Nine Dragon Tree Conjecture, which is a refinement of Nash-Williams Theorem. They asked if for every integer k and d, if a graph G has every subgraph H having at most |V(H)|(k + d/(k+d+1)) edges, then G can be coloured using k+1 colours such that each colour class induces a forest, and further one of the colour classes induces a forest where every connected component has at most d edges. This conjecture is only known to be true when d = 1 (Yang) and k= 1 and d=2 (Kim et al.) I'll discuss some recent progress which shows that the k = 1, d = 3 case is effectively true, and some possible extensions to list versions, as well as pseudoforest and other analogues of the conjecture. This is joint work with Evelyne Smith Roberge, Zishen (Jason) Qu, and Ronen Wdowinski.