Title: A Pseudoforest Analogue of the Strong Nine Dragon Tree Conjecture
|Affiliation:||University of Waterloo|
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.
200 University Avenue West
Waterloo, ON N2L 3G1