Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777647 | Journal of Combinatorial Theory, Series B | 2017 | 18 Pages |
Abstract
The Tree Decomposition Conjecture by Barát 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 simple 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. We call such a subgraph a homomorphic copy of T. This implies the Tree Decomposition Conjecture under the additional constraint that the girth of G is greater than the diameter of T. As an application, we verify the Tree Decomposition Conjecture for all trees of diameter at most 4.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Martin Merker,