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

DOI10.1016/J.JCTB.2016.05.005zbMATH Open1350.05081arXiv1603.00198OpenAlexW2964047817MaRDI QIDQ345073FDOQ345073

Authors: Martin Merker 

Publication date: 25 November 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: The Tree Decomposition Conjecture by Bar'at 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.

Full work available at URL: https://arxiv.org/abs/1603.00198

Recommendations

• Edge-decomposition of graphs into copies of a tree with four edges
• Decomposing highly edge-connected graphs into paths of any given length
• Decomposing graphs into paths and trees
• A proof of the Barát-Thomassen conjecture
• Edge‐decomposing graphs into coprime forests

zbMATH Keywords

treesedge connectivityedge decomposition

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• A Reduction Method for Edge-Connectivity in Graphs
• The weak 3-flow conjecture and the weak circular flow conjecture
• Edge-decompositions of highly connected graphs into paths
• Decomposing graphs into paths of fixed length
• Decompositions of highly connected graphs into paths of length 3
• On partitioning the edges of graphs into connected subgraphs
• Edge-decomposition of graphs into copies of a tree with four edges
• Decomposing a graph into bistars
• Claw‐decompositions and tutte‐orientations
• On a theorem of Mader
• Spanning trees and spanning Eulerian subgraphs with small degrees
• Connected \((g,f)\)-factors
• On low bound of degree sequences of spanning trees inK-edge-connected graphs
• Bounded degree spanning trees (extended abstract)

Cited In (10)

• Decomposing graphs into paths and trees
• Edge‐decomposing graphs into coprime forests
• Decompositions of graphs into trees
• Directed tree decompositions of Cayley digraphs with word-degenerate connection sets
• Edge-decomposition of graphs into copies of a tree with four edges
• Claw‐decompositions and tutte‐orientations
• Edge-decompositions ofK_n,ninto isomorphic copies of a given tree
• Modulo orientations with bounded out-degrees
• Tree-thickness and caterpillar-thickness under girth constraints
• A proof of the Barát-Thomassen conjecture

This page was built for publication: Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree

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