GT
Seminars are given every Friday from 2:00 to 3:00 (usually in room 178, but not for the time being). You are welcome 10 minutes earlier for tea, coffee and cake.
In order to receive the announcements, just send an email to sympa@diff.u-bordeaux.fr with subject "subscribe labri.go-gt Cookie Monster", where Cookie is your first name and Monster your last name.
See the agenda of the seminars: webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.html https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.html; to add it to yours webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.ics https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics , or flash the following QRCode:
Next talks:
The online talks are available here : https://webconf.u-bordeaux.fr/b/mar-ef4-zed.
Vendredi 12 Décembre à 14h - Lukas Michel
New bounds for linear arboricity and short tours in regular graphs
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.

