Graphs and Matroids Seminar - Logan Grout

Title: A Pseudoforest Analogue of the Strong Nine Dragon Tree Conjecture

Abstract:

In 2016, Jiang and Yang proved the Nine Dragon Tree Conjecture, a strengthening of the classical arboricity result of Nash-Williams (1964). On the way to developing this proof, Fan, Lim Song, and Yang proved an analogous result for decomposing graphs into pseudoforests, which is a strengthening of Hakimi’s Theorem.

We attempt to follow the same path and prove a pseudo forest analogue of the Strong Nine Dragon Tree Conjecture: that, for any positive integers k and d, if  G is a graph with maximum average degree at most 2k+2d/(k+d+1), then G decomposes into k+1 pseudoforests, with one of these pseudoforests containing components with at most d edges.