14:00
15:00

The celebrated Linear Arboricity Conjecture of Akiyama, Exoo, and Harary from 1980 asserts that the edges of every graph with maximum degree Δ can be decomposed into at most ⌈(Δ+1)/2⌉ linear forests, where a linear forest is a collection of vertex-disjoint paths. We show that any graph on n vertices can be decomposed into at most Δ/2 + O(log n) linear forests. This improves the previous best bound for Δ = Ω(log^2 n).

Along the way, we show that any d-regular graph on n vertices has a spanning linear forest with at most 2 * n/(d+1) paths. This resolves a conjecture of Feige and Fuchs and confirms a well-known conjecture of Magnant and Martin up to a factor of 2. As a corollary, it also follows that every connected d-regular graph on n vertices has a tour of length at most (1+O(1/d)) * n. This is optimal and improves bounds of Vishnoi and of Feige, Ravi, and Singh, but we do not obtain an efficient algorithm for computing such a tour.

(Lukas Michel) [University of Oxford]
https://people.maths.ox.ac.uk/michel

Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

English
LaBRI/178