Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree

详细信息    查看全文

• 作者：Martin Merker ^{marmer@dtu.dk}
• 关键词：Edge-decomposition ; Trees ; Edge-connectivity
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：91-108
• 全文大小：410 K
• 卷排序：122

文摘

The Tree Decomposition Conjecture by Barát and Thomassen states that for every tree T   there exists a natural number k(T)k(T) such that the following holds: If G   is a k(T)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.