Edge-partitioning 3-edge-connected graphs into paths

2019/07/26 by Tereza Klimošová, Klimošová, Tereza, Stéphan Thomassé +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #VLSI and FPGA Design Techniques

paper · pdf · doi:10.48550/arxiv.1907.11600

openalex publication_date 2019/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We show that for every l, there exists d_l such that every 3-edge-connected graph with minimum degree d_l can be edge-partitioned into paths of length l (provided that its number of edges is divisible by l). This improves a result asserting that 24-edge-connectivity and high minimum degree provides such a partition. This is best possible as 3-edge-connectivity cannot be replaced by 2-edge connectivity.

Related

• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
• Length 3 Edge-Disjoint Paths and Partial Orientation
• Edge-decomposing graphs into coprime forests
• Minimum degree of 3-graphs without long linear paths
• A synthesis for exactly 3-edge-connected graphs