Decompositions of highly connected graphs into paths of length five

DOI10.1016/J.ENDM.2015.07.036zbMATH Open1347.05106arXiv1505.04309OpenAlexW2963595382MaRDI QIDQ324786FDOQ324786

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

Publication date: 17 October 2016

Abstract: We study the Decomposition Conjecture posed by Bar'at and Thomassen (2006), which states that for every 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 $G$ admits a decomposition into copies of $T$. In a series of papers, Thomassen verified this conjecture for stars, some bistars, paths of length $3$, and paths whose length is a power of $2$. We verify the Decomposition Conjecture for paths of length $5$.

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

Recommendations

• Decomposing highly connected graphs into paths of length five
• Decompositions of highly connected graphs into paths of any given length
• Decomposing highly edge-connected graphs into paths of any given length
• Decomposing graphs into paths of fixed length
• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture

zbMATH Keywords

path decompositionedge decompositionhighly connected

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The weak 3-flow conjecture and the weak circular flow conjecture
• Title not available (Why is that?)
• Edge-decompositions of highly connected graphs into paths
• Decompositions of triangle-free 5-regular graphs into paths of length five
• Decomposing graphs into paths of fixed length
• Decompositions of highly connected graphs into paths of length 3
• Edge-decomposition of graphs into copies of a tree with four edges
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Decomposing a graph into bistars
• Claw‐decompositions and tutte‐orientations

Cited In (7)

• Decomposing graphs into paths and trees
• Edge‐decomposing graphs into coprime forests
• Path decompositions of regular graphs with prescribed girth
• Decompositions of highly connected graphs into paths of any given length
• Decomposing highly edge-connected graphs into paths of any given length
• Decomposing highly connected graphs into paths of length five
• Decomposing regular graphs with prescribed girth into paths of given length

This page was built for publication: Decompositions of highly connected graphs into paths of length five

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