BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:b6a68735-fa5c-40f4-b1b7-4e963a36454f
X-WR-CALNAME:[gt.go] - 'From Hex to the disjoint separators problem' by Flo
 rian Galliot
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20280326T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20251026T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20261025T030000
RDATE:20271031T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20260329T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20270328T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:b6a68735-fa5c-40f4-b1b7-4e963a36454f
DTSTAMP:20260513T073804Z
CLASS:PUBLIC
DESCRIPTION:Hex is a board game\, where two players take turns placing red 
 and blue stones respectively on a rhombus-shaped board with hexagonal cell
 s\, with the goal of connecting the two opposite red sides or the two oppo
 site blue sides of the board respectively. A well-known result is that the
  game cannot end in a draw\, no matter how the players play. \n\nWe are in
 terested in the structural properties of the Hex board that cause this phe
 nomenon. To answer this question\, we generalize the game as follows. We a
 re given a graph G with four terminals: one red source s_r\, one red targe
 t t_r\, one blue source s_b\, and one blue target t_b. The players take tu
 rns coloring vertices in red and blue respectively\, trying to get a monoc
 hromatic path between the two terminals of their color. The game ends in a
  draw if and only if the blue vertices form an (s_r\,t_r)-separator and th
 e red vertices form an (s_b\,t_b)-separator. Therefore\, we study the prob
 lem\, given (G\,s_r\,t_r\,s_b\,t_b)\, of the existence of an (s_r\,t_r)-se
 parator and an (s_b\,t_b)-separator which are disjoint. \n\nWe solve 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 fo
 r planar graphs if we allow for an unbounded number of red and blue termin
 als. \n\nJoint work with T. Delépine\, Y. Mogge\, L. Montero and N. Schivr
 e. \n\n(Florian Galliot) [Institut de Mathématiques de Marseille] \n\n\nVé
 rifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [
  https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | ht
 tps://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ] \n\nR
 emarks / Remarques \n\nFind all the information of the working group on th
 is [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=
 en | web page ] . \nRetrouvez toutes les informations du GT sur cette [ ht
 tps://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] . 
 \n\n\n\nImport automatique depuis https://webmel.u-bordeaux.fr/home/bf-lab
 ri.ca@u-bordeaux.fr/gt.go.ics par sync_icals_to_drupal.py pour GT-GO
DTSTART;TZID=Europe/Paris:20260507T140000
DTEND;TZID=Europe/Paris:20260507T150000
LOCATION:LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'From Hex to the disjoint separators problem' by Florian 
 Galliot
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
