## On Gallai's conjecture for series-parallel graphs and planar 3-trees. (arXiv:1706.04130v1 [math.CO])

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 \$\lceil n/2 \rceil\$ 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 \$\lfloor 5n/8 \rfloor\$ paths, which is an improvement over the best previously known bound of \$\lfloor 2n/3 \rfloor\$.查看全文

## Solidot 文章翻译

 你的名字 留空匿名提交 你的Email或网站 用户可以联系你 标题 简单描述 内容 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 \$\lceil n/2 \rceil\$ 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 \$\lfloor 5n/8 \rfloor\$ paths, which is an improvement over the best previously known bound of \$\lfloor 2n/3 \rfloor\$.