Évènement

Florian Galliot
I2M
https://www.i2m.univ-amu.fr/perso/galliot.f/

Date(s) : 26/05/2026   iCal
11h00 - 12h00

Hex is a board game, where two players take turns placing red and blue stones respectively on a rhombus-shaped board with hexagonal cells, with the goal of connecting the two opposite red sides or the two opposite 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. We are interested in the structural properties of the Hex board that cause 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 players take turns coloring vertices in red and blue respectively, trying to get a monochromatic 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 the red vertices form an (s_b,t_b)-separator. Therefore, we study 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 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 for planar graphs if we allow for an unbounded number of red and blue terminals. Joint work with T. Delépine, Y. Mogge, L. Montero and N. Schivre.

Emplacement
I2M Luminy - TPR2, Salle de Séminaire 304-306 (3ème étage)

Catégories

• Séminaire