Decomposing highly edge-connected graphs into paths of any given length

DOI10.1016/J.JCTB.2016.07.010zbMATH Open1350.05075arXiv1509.06393OpenAlexW2963030845MaRDI QIDQ345101FDOQ345101

Authors: M. T. I. Oshiro, Yoshiko Wakabayashi, F. Botler, G. O. Mota 

Publication date: 25 November 2016

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

Abstract: In 2006, Bar'at and Thomassen posed the following conjecture: for each tree $T$, there exists a natural number $k_T$ such that, if $G$ is a $k_T$-edge-connected graph and $|E(G)|$ is divisible by $|E(T)|$, then $G$ admits a decomposition into copies of $T$. This conjecture was verified for stars, some bistars, paths of length $3$, $5$, and $2^r$ for every positive integer $r$. We prove that this conjecture holds for paths of any fixed length.

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

Recommendations

• Decompositions of highly connected graphs into paths of any given length
• Decomposing highly connected graphs into paths of length five
• Decompositions of highly connected graphs into paths of length five
• Decomposing graphs into paths of fixed length
• Decomposing graphs into paths and trees

zbMATH Keywords

decompositionconnectivitypath

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graph theory
• Title not available (Why is that?)
• 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
• Factors and factorizations of graphs. Proof techniques in factor theory
• The weak 3-flow conjecture and the weak circular flow conjecture
• Edge-decompositions of highly connected graphs into paths
• Decomposing highly connected graphs into paths of length five
• Decompositions of triangle-free 5-regular graphs into paths of length five
• Decomposing regular graphs with prescribed girth into paths of given length
• Decomposing graphs into paths of fixed length
• Decomposing series-parallel graphs into paths of length 3 and triangles
• Decompositions of highly connected graphs into paths of any given length
• Decompositions of highly connected graphs into paths of length five
• Decompositions of highly connected graphs into paths of length 3
• Edge-decomposition of graphs into copies of a tree with four edges
• Title not available (Why is that?)
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Decomposing a graph into bistars
• Claw‐decompositions and tutte‐orientations
• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
• Connected \((g,f)\)-factors
• Connected Detachments of Graphs and Generalized Euler Trails

Cited In (19)

• Decomposing graphs into paths and trees
• Decompositions of highly connected graphs into paths of length 3
• Edge‐decomposing graphs into coprime forests
• Decomposing 8-regular graphs into paths of length 4
• Decompositions of highly connected graphs into paths of any given length
• Decompositions of highly connected graphs into paths of length five
• Edge-decomposition of graphs into copies of a tree with four edges
• Decomposing a graph into bistars
• Locally self-avoiding Eulerian tours
• Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree
• Edge-decompositions of highly connected graphs into paths
• Cycle decompositions in \(k\)-uniform hypergraphs
• Decomposing highly connected graphs into paths of length five
• Decomposing graphs into long paths
• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
• Hamilton path decompositions of complete multipartite graphs
• Decomposing regular graphs with prescribed girth into paths of given length
• A proof of the Barát-Thomassen conjecture
• Decomposing graphs into paths of fixed length

This page was built for publication: Decomposing highly edge-connected graphs into paths of any given length

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