The nine dragon tree conjectures

Abstract

This thesis deals with the Nine Dragon Tree conjectures, which concern partitioning the edge set of a graph into as few forests as possible while ensuring that one of the forests is as "sparse" as possible. The well-known Nash-Williams Theorem states that the edge set of a loopless graph G can be partitioned into k forests if γ(G) := \max_{H \subseteq G, v(H) > 1} e(H)/(v(H) - 1) <= k. Thus, \ceil{γ(G)} is the minimum number of forests into which E(G) can be partitioned. The Nine Dragon Tree Theorem generalizes this relationship: if k, d \in N and γ(G) <= k + d/(d+k+1), then G admits a decomposition into k+1 forests, where one of the forests F has maximum degree at most d. The Strong Nine Dragon Tree Conjecture even states that a decomposition can be found in which each tree of F contains at most d edges. While the Nine Dragon Tree Theorem has already been proven, its strong variant remains open in most cases. In this thesis, we prove it for d <= 2(k+1) and show an approximation for the remaining cases in which the sizes of the connected components are bounded by O(d^2/k). We also show that, as conjectured by Kim, Kostochka, West, Wu, and Zhu, there exists a weaker density condition that still implies the stated decompositions. Analogous conjectures can be formulated for pseudoforests, for which even the strong variant has already been proven. In this thesis, we show that an even stronger decomposition is possible in which one of the pseudoforests F is actually a forest, and its diameter can be further restricted. We prove that the diameter bounds we establish are best possible, in the case that F is also required to have its degree bounded above by any constant. We further show that, as in the case of the Nine Dragon Tree conjectures for forests, a weaker density condition exists for the pseudoforest variants that also allows us to achieve the additional diameter bounds.