An Approximate Version of the Strong Nine Dragon Tree Conjecture

arXiv1909.07946MaRDI QIDQ6325494FDOQ6325494

Benjamin Moore

Publication date: 17 September 2019

Abstract: The Strong Nine Dragon Tree Conjecture asserts that for any integers $k$ and $d$ any graph with fractional arboricity at most $k+fracdd+k+1$ decomposes into $k+1$ forests, such that for at least one of the forests, every connected component contains at most $d$ edges. We prove this conjecture when $dleqk+1$. We also prove an approximate version of this conjecture, that is, we prove that for any positive integers $k$ and $d$, any graph with fractional arboricity at most $k+fracdd+k+1$ decomposes into $k+1$ forests, such that one for at least one of the forests, every connected component contains at most $d+fracd(k(2lceilfracdk+1+2ceil{)}^{lceilfracdk+1+2)ceil}-k)k+1$ edges.

This page was built for publication: An Approximate Version of the Strong Nine Dragon Tree Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325494)