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}, }
Christoph Doppelbauer | 10.05.2024