Decomposing highly edge-connected graphs into trees of small diameter

Martin Merker
Technical University of Denmark



Content: The Tree Decomposition Conjecture by B\'arat and Thomassen states that for every tree $T$ there exists a natural number $k(T)$ such that the following holds: If $G$ is a $k(T)$-edge-connected graph with size divisible by the size of $T$, then $G$ can be edge-decomposed into subgraphs isomorphic to $T$. So far this conjecture has only been verified for paths, stars, and a family of bistars. We prove a weaker version of the Tree Decomposition Conjecture, where we require the subgraphs in the decomposition to be isomorphic to graphs that can be obtained from $T$ by vertex-identifications. This implies the Tree Decomposition Conjecture under the additional constraint that the girth of $G$ is greater than the diameter of $T$. We also show that the Tree Decomposition Conjecture holds for all trees of diameter at most 4, as well as for some trees of diameter 5.

Back to all abstracts