# Veröffentlichung

Titel:
On Gallai's conjecture for series-parallel graphs and planar 3-trees
AutorInnen:
Philipp Kindermann
Lena Schlipf
André Schulz
Kategorie:
Sonstiges
erschienen in:
CoRR, Vol. abs/1706.04130, 2017
Abstract:

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 n/2 paths. We prove Gallai's conjecture for series-parallel graphs. For the class of planar 3-trees we show how to construct a path cover with at most 5n/8 paths, which is an improvement over the best previously known bound of 2n/3.