BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:bce67ed9-cd84-44bf-9195-aa5ca70aa7d8
X-WR-CALNAME:[gt.go] - 'New bounds for linear arboricity and short tours in
  regular graphs' by Lukas Michel
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20271031T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20251026T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20261025T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20250330T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20260329T020000
RDATE:20270328T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:bce67ed9-cd84-44bf-9195-aa5ca70aa7d8
DTSTAMP:20260404T093724Z
CLASS:PUBLIC
DESCRIPTION:The celebrated Linear Arboricity Conjecture of Akiyama\, Exoo\,
  and Harary from 1980 asserts that the edges of every graph with maximum d
 egree Δ 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 g
 raph on n vertices can be decomposed into at most Δ/2 + O(log n) linear fo
 rests. This improves the previous best bound for Δ = Ω(log^2 n). \n\nAlong
  the way\, we show that any d-regular graph on n vertices has a spanning l
 inear 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 Marti
 n up to a factor of 2. As a corollary\, it also follows that every connect
 ed 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\, a
 nd Singh\, but we do not obtain an efficient algorithm for computing such 
 a tour. \n\n(Lukas Michel) [University of Oxford] \nhttps://people.maths.o
 x.ac.uk/michel \n\nVérifiez que vous êtes bien inscrits sur le site du [gd
 r-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes
 /Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Eq
 uipes#membres ] \n\nRemarks / Remarques \n\nFind all the information of th
 e working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.ph
 p/Groupe/GT?userlang=en | web page ] . \nRetrouvez toutes les informations
  du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Group
 e/GT | page web ] . \n\n\n\nImport automatique depuis https://webmel.u-bor
 deaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics par sync_icals_to_drupal
 .py pour GT-GO
DTSTART;TZID=Europe/Paris:20251212T140000
DTEND;TZID=Europe/Paris:20251212T150000
LOCATION:LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'New bounds for linear arboricity and short tours in regu
 lar graphs' by Lukas Michel
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
