GT
Les GT se tiennent chaque vendredi de 14h à 15h (d'ordinaire en salle 178). Vous êtes invités à venir 10 minutes avant pour partager thé, café et gâteaux.
Pour vous inscrire à la liste de diffusion, il suffit d'envoyer un mail à sympa@diff.u-bordeaux.fr avec pour sujet "subscribe labri.go-gt Cookie Monster", où Cookie est remplacé par votre prénom et Monster par votre nom.
Voir l'agenda des GT: 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; pour l'ajouter au vôtre, 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 ou bien flasher le QRCode suivant:
Prochains exposés :
Les exposés en ligne sont accessibles à cette adresse : 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.

