BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20250330T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20251026T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20250610T104500
DTEND;TZID=Europe/Paris:20250610T114500
DTSTAMP:20260419T093416
CREATED:20250416T144328Z
LAST-MODIFIED:20250502T081035Z
UID:11836-1749552300-1749555900@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Fractional domatic number and minimum degree »\, Hugo Demaret (Ecole Polytechnique et GREYC)
DESCRIPTION:The domatic number of a graph G is the maximum number of pairwise disjoint dominating sets of G. We are interested in the LP-relaxation of this parameter\, which is called the fractional domatic number of G. We study its extremal value in the class of graphs of minimum degree d. The fractional domatic number of a graph of minimum degree d is always at most d+1\, and at least (1-o(1))d/ln d as d goes to infinity. This is asymptotically tight even within the class of split graphs. \nOur main result concerns the case d=2. We show that\, excluding 8 exceptional graphs\, the fractional domatic number of every connected graph of minimum degree at least 2 is at least 5/2. We also show that this bound cannot be improved if only finitely many graphs are excluded\, even when restricting to bipartite graphs of girth at least 6. This proves in a stronger sense a conjecture by Gadouleau\, Harms\, Mertzios\, and Zamaraev (2024). This also extends and generalises results from McCuaig and Shepherd (1989)\, from Fujita\, Kameda\, and Yamashita (2000)\, and from Abbas\, Egerstedt\, Liu\, Thomas\, and Whalen (2016). Finally\, we show that planar graphs of minimum degree at least 2 and girth at least g have fractional domatic number at least 3-O(1/g) as g goes to infinity.\nWe present these results and provide insights into the proof. \nThis is a joint work with Quentin Chuet\, Hoang La and François Pirot.
URL:https://www.greyc.fr/event/seminaire-algorithmique-hugo-demaret-ecole-polytechnique-et-greyc/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
END:VCALENDAR