- This event has passed.
Atlantic Graph Theory Seminar: Melissa Huggan (Mount Allison)
February 2, 2022 @ 3:30 pm - 4:30 pm
The Orthogonal Colouring Game
The Orthogonal Colouring Game is a combinatorial game in which two players alternately colour vertices of a pair of isomorphic graphs while respecting the properness and the orthogonality of the colouring. Each player aims to maximize her score, which is the number of coloured vertices in the copy of the graph she owns. An involution $\sigma$ of a graph $G$ is strictly matched if its fixed point set induces a clique and any non-fixed point $v \in V(G)$ is connected with its image $\sigma(v)$ by an edge.
In this talk, we introduce the game and our main result that the second player has a strategy to force a draw in this game for graphs that admit a strictly matched involution. We will also give a structural characterization of graphs admitting a strictly matched involution.
This is joint work with Stephan Dominique Andres, Francois Dross, Fionn Mc Inerney, and Richard J. Nowakowski.
Join Zoom Meeting: link