On Gallai's conjecture for series-parallel graphs and planar 3-trees

Philipp Kindermann, Lena Schlipf, André Schulz

A path cover is a decomposition of the edges of a graph into edge-disjoint simple paths. Gallai conjectured that every connected $n$-vertex graph has a path cover with at most $\lc…