Edge-decomposition of graphs into copies of a tree with four edges

zbMATH Open1300.05243arXiv1203.1671MaRDI QIDQ405153FDOQ405153

Authors: János Barát, Dániel Gerbner 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We study edge-decompositions of highly connected graphs into copies of a given tree. In particular we attack the following conjecture by Bar'at and Thomassen: for each tree $T$, there exists a natural number $k_T$ such that if $G$ is a $k_T$-edge-connected graph, and $|E(T)|$ divides $|E(G)|$, then $E(G)$ has a decomposition into copies of $T$. As one of our main results it is sufficient to prove the conjecture for bipartite graphs. Let $Y$ be the unique tree with degree sequence $(1,1,1,2,3)$. We prove that if $G$ is a 191-edge-connected graph of size divisible by 4, then $G$ has a $Y$-decomposition. This is the first instance of such a theorem, in which the tree is different from a path or a star.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree
• Decomposing highly edge-connected graphs into paths of any given length
• Edge‐decomposing graphs into coprime forests
• Decompositions of highly connected graphs into paths of any given length
• A proof of the Barát-Thomassen conjecture

zbMATH Keywords

treedecompositionedge-connectivity

Mathematics Subject Classification ID

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

Cites Work

• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Edge-connectivity and edge-disjoint spanning trees
• The weak 3-flow conjecture and the weak circular flow conjecture
• Edge-decompositions of highly connected graphs into paths
• Decompositions of highly connected graphs into paths of length 3
• On partitioning the edges of graphs into connected subgraphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Decomposing a graph into bistars
• Claw‐decompositions and tutte‐orientations
• Connected \((g,f)\)-factors

Cited In (15)

• Decomposing graphs into paths and trees
• Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm
• Spanning trees and spanning Eulerian subgraphs with small degrees
• FORK-DECOMPOSITION OF DIRECT PRODUCT OF GRAPHS
• Edge‐decomposing graphs into coprime forests
• Decompositions of highly connected graphs into paths of any given length
• Decompositions of highly connected graphs into paths of length five
• Decomposing highly edge-connected graphs into paths of any given length
• Decomposing a graph into bistars
• Claw‐decompositions and tutte‐orientations
• Edge-decompositions ofK_n,ninto isomorphic copies of a given tree
• Modulo orientations with bounded out-degrees
• Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree
• Decomposing highly connected graphs into paths of length five
• A proof of the Barát-Thomassen conjecture

This page was built for publication: Edge-decomposition of graphs into copies of a tree with four edges

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