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

DOI10.1016/J.JCTB.2016.05.005MaRDI QIDQ345073zbMATHOpenAlexFDO

Authors Martin Merker

Publication date 25 November 2016

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

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

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)

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.

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

Cites work

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

Cited in

(10)

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

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)