New bounds for linear arboricity and related problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912504930631680 |
|---|---|
| author | Christoph, Micha Draganić, Nemanja Girão, António Hurley, Eoin Michel, Lukas Müyesser, Alp |
| author_facet | Christoph, Micha Draganić, Nemanja Girão, António Hurley, Eoin Michel, Lukas Müyesser, Alp |
| contents | A linear forest is a collection of vertex-disjoint paths. The Linear Arboricity Conjecture states that every graph of maximum degree $Δ$ can be decomposed into at most $\lceil(Δ+1)/2\rceil$ linear forests. We prove that $Δ/2 + \mathcal{O}(\log n)$ linear forests suffice, where $n$ is the number of vertices of the graph. If $Δ= Ω(n^\varepsilon)$, this is an exponential improvement over the previous best error term. We achieve this by generalising Pósa rotations from rotations of one endpoint of a path to simultaneous rotations of multiple endpoints of a linear forest. This method has further applications, including the resolution of a conjecture of Feige and Fuchs on spanning linear forests with few paths and the existence of optimally short tours in connected regular graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20500 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New bounds for linear arboricity and related problems Christoph, Micha Draganić, Nemanja Girão, António Hurley, Eoin Michel, Lukas Müyesser, Alp Combinatorics A linear forest is a collection of vertex-disjoint paths. The Linear Arboricity Conjecture states that every graph of maximum degree $Δ$ can be decomposed into at most $\lceil(Δ+1)/2\rceil$ linear forests. We prove that $Δ/2 + \mathcal{O}(\log n)$ linear forests suffice, where $n$ is the number of vertices of the graph. If $Δ= Ω(n^\varepsilon)$, this is an exponential improvement over the previous best error term. We achieve this by generalising Pósa rotations from rotations of one endpoint of a path to simultaneous rotations of multiple endpoints of a linear forest. This method has further applications, including the resolution of a conjecture of Feige and Fuchs on spanning linear forests with few paths and the existence of optimally short tours in connected regular graphs. |
| title | New bounds for linear arboricity and related problems |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.20500 |