Gallai's path decomposition conjecture for graphs of small maximum   degree
  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. 
Marthe Bonamy, Thomas Perrett
math.CO cs.DM