Beijing Institute of Mathematical Sciences and Applications

Jie Ma , Benjamin Sudakov

Nemanja Draganic

Tuesday, April 21, 2026 5:05 PM - 6:15 PM

Online

Zoom 787 662 9899 (BIMSA)

A linear forest is a collection of vertex-disjoint paths. The Linear Arboricity Conjecture (Akiyama, Exoo, and Harary, 1980) posits that the edges of every graph of maximum degree $\Delta$ can be decomposed into at most $\lceil(\Delta+1)/2\rceil$ linear forests. In this talk, I will present our recent work showing that $\Delta/2 + \mathcal{O}(\log n)$ linear forests suffice for an n-vertex graph. For $\Delta = \Omega(n^\varepsilon)$, this yields an exponential improvement over previously known error terms. The core of the proof relies on a novel technique that generalizes Pósa rotations, extending the operation from a single path endpoint to the simultaneous rotation of multiple endpoints in a linear forest. We will also discuss the application of this method to resolve a conjecture of Feige and Fuchs, which states that every d-regular graph on n vertices admits a spanning linear forest consisting of at most $\mathcal{O}(n/d)$ paths. Finally, we will use this method to establish the existence of optimally short tours in connected regular graphs. This is joint work with Micha Christoph, António Girão, Eoin Hurley, Lukas Michel, and Alp Müyesser.