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⌋.

Download:

arXiv

BibTeX-Eintrag:

@article{, author = { Philipp Kindermann and Lena Schlipf and Andr\’e Schulz }, title = { On Gallai's conjecture for series-parallel graphs and planar 3-trees }, journal = {CoRR}, volume = { abs/1706.04130}, year = {2017}, url = { https://arxiv.org/abs/1706.04130}, }