BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:daf76b2d-9163-47e7-bf2b-bd189754cdda
X-WR-CALNAME:[gt.go] - 'Smaller Universal Graphs for Caterpillars and Graph
 s of Bounded Path-Width ' by Cyril Gavoille
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20241027T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20211031T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20221030T030000
RDATE:20231029T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20220327T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20230326T020000
RDATE:20240331T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:daf76b2d-9163-47e7-bf2b-bd189754cdda
DTSTAMP:20260426T065241Z
CLASS:PUBLIC
DESCRIPTION:/Exposé en français/Talk in french / English slides / transpare
 nts en anglais \n\nIn this talk\, I will given a rather simple constructio
 n of a graph U n with at most 8n vertices with the property that every n-v
 ertex caterpillar is isomorphic to some induced-subgraph of U n . Previous
  constructions of so-called induced-universal graph for caterpillars used 
 256n vertices in the best (Bonichon et al. SIROCCO'06 and Alstrup et al. F
 OCS'15). \n\nThen\, I will also present an extension to path-width-p graph
 s with an induced-universal graph of n.2 O(p) vertices. This is complement
 ed with a n.2 Ω(p) lower bound. With bounded path-width graphs\, our const
 ruction considerably enlarge the family of n-vertex graphs having an induc
 ed-universal graph of O(n) vertices\, which is optimal. Such unexpected pr
 operty was known only for trees\, bounded maximum degree outerplanar graph
 s and maximum degree-2 graphs. \n\nThe extended result is obtained from an
  algorithmic approach by designing an adjacency labeling scheme for these 
 graphs using log(n) + O(p) bit vertex labels and with a constant time adja
 cency test. \n\nThis is a joint with Arnaud Labourel. \n\n\n[Cyril Gavoill
 e] (Université de Bordeaux\, Labri ) \n\nhttps://dept-info.labri.fr/~gavoi
 lle/ \n\n\nRemarks / Remarques \n\nFind all the information of the working
  group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/
 GT?userlang=en | web page ] . \nRetrouvez toutes les informations du GT su
 r cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | pa
 ge web ] .
DTSTART;TZID=Europe/Paris:20221007T140000
DTEND;TZID=Europe/Paris:20221007T150000
LOCATION:https://webconf.u-bordeaux.fr/b/mar-ef4-zed ou au LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'Smaller Universal Graphs for Caterpillars and Graphs of 
 Bounded Path-Width ' by Cyril Gavoille
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
