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

DOI10.1016/J.JCTB.2016.07.010zbMath1350.05075arXiv1509.06393OpenAlexW2963030845MaRDI QIDQ345101

Marcio T. I. Oshiro, Yoshiko Wakabayashi, Fábio Botler, Guilherme Oliveira Mota

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/1509.06393

zbMATH Keywords

decompositionconnectivitypath

Mathematics Subject Classification ID

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

Related Items (8)

Decomposing 8-regular graphs into paths of length 4 ⋮ Decomposing regular graphs with prescribed girth into paths of given length ⋮ Edge‐decomposing graphs into coprime forests ⋮ Decomposing graphs into paths and trees ⋮ Hamilton path decompositions of complete multipartite graphs ⋮ A proof of the Barát-Thomassen conjecture ⋮ Decomposing highly connected graphs into paths of length five ⋮ Locally self-avoiding Eulerian tours

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Edge-decomposition of graphs into copies of a tree with four edges
• The weak 3-flow conjecture and the weak circular flow conjecture
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• Decomposing a graph into bistars
• Factors and factorizations of graphs. Proof techniques in factor theory
• Edge-decompositions of highly connected graphs into paths
• Decomposing highly connected graphs into paths of length five
• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
• 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
• Connected (g, f)-factors
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Decompositions of highly connected graphs into paths of length 3
• Connected Detachments of Graphs and Generalized Euler Trails
• A Reduction Method for Edge-Connectivity in Graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Claw‐decompositions and tutte‐orientations

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