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