BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:9100@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20260526T110000
DTEND;TZID=Europe/Paris:20260526T120000
DTSTAMP:20260519T085245Z
URL:https://www.i2m.univ-amu.fr/evenements/from-hex-to-the-disjoint-separa
 tors-problem-in-graphs/
SUMMARY:Florian Galliot (I2M): From Hex to the disjoint separators problem 
 in graphs
DESCRIPTION:Florian Galliot: Hex is a board game\, where two players take t
 urns placing red and blue stones respectively on a rhombus-shaped board wi
 th hexagonal cells\, with the goal of connecting the two opposite red side
 s or the two opposite blue sides of the board respectively. A well-known r
 esult is that the game cannot end in a draw\, no matter how the players pl
 ay. We are interested in the structural properties of the Hex board that c
 ause this phenomenon. To answer this question\, we generalize the game as 
 follows. We are given a graph G with four terminals: one red source s_r\, 
 one red target t_r\, one blue source s_b\, and one blue target t_b. The pl
 ayers take turns coloring vertices in red and blue respectively\, trying t
 o get a monochromatic path between the two terminals of their color. The g
 ame ends in a draw if and only if the blue vertices form an (s_r\,t_r)-sep
 arator and the red vertices form an (s_b\,t_b)-separator. Therefore\, we s
 tudy the problem\, given (G\,s_r\,t_r\,s_b\,t_b)\, of the existence of an 
 (s_r\,t_r)-separator and an (s_b\,t_b)-separator which are disjoint. We so
 lve this problem in polynomial time for planar graphs. Moreover\, we show 
 that this problem is NP-complete for graphs of distance-to-planar at most 
 4\, or for planar graphs if we allow for an unbounded number of red and bl
 ue terminals. Joint work with T. Delépine\, Y. Mogge\, L. Montero and N. 
 Schivre.
CATEGORIES:Séminaire,Ernest
LOCATION:I2M Luminy - TPR2\, Salle de Séminaire 304-306 (3ème étage)\, 1
 63 Avenue de Luminy\, Marseille\, 13009\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=163 Avenue de Luminy\, Mars
 eille\, 13009\, France;X-APPLE-RADIUS=100;X-TITLE=I2M Luminy - TPR2\, Sall
 e de Séminaire 304-306 (3ème étage):geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20260329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR