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

MaRDI QIDQ405153zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1203.1671, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p55

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

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)

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.

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

Cites work

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

Cited in

(15)

• A proof of the Barát-Thomassen conjecture
• 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
• Edge-decompositions ofK_n,ninto isomorphic copies of a given tree
• Claw‐decompositions and tutte‐orientations
• 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

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)