Gallai's path decomposition conjecture for graphs of small maximum degree

2016/09/20 by Bonamy, Marthe, Perrett, Thomas · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1609.06257

Abstract

Gallai's path decomposition conjecture states that the edges of any connected graph on n vertices can be decomposed into at most (n+1)/2 paths. We confirm that conjecture for all graphs with maximum degree at most five.

Cited by

• Path decompositions of Eulerian graphs
• Tight Bounds for Cycle-Edge Decompositions and Covers

Related

• Towards Gallai's path decomposition conjecture
• Gallai's path decomposition in planar graphs
• Gallai's path decomposition conjecture for triangle-free planar graphs
• Gallai's Conjecture for Complete and "Nearly Complete" Graphs
• Path decompositions of Eulerian graphs