Edge-partitioning 3-edge-connected graphs into paths

Abstrakt

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.(c) 2022 Elsevier Inc. All rights reserved.

Klíčová slova

• Edge-decomposition
• Barat-Thomassen conjecture
• Decomposition into paths