Decompositions of highly connected graphs into paths of length five

2015/05/16 by Botler, Fábio, Mota, Guilherme O., Oshiro, Marcio T. I. +1
#05C38 #05C51 #05C70 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1505.04309

Abstract

We study the Decomposition Conjecture posed by Barát 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.

Related

• Decomposing highly edge-connected graphs into paths of any given length
• Edge-decomposition of graphs into copies of a tree with four edges
• Decomposing highly edge-connected graphs into homomorphic copies of a\n fixed tree
• A Proof of the Barát-Thomassen Conjecture
• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture