The Orthogonal Colouring Game

Stephan Dominique Andres 1 Fionn Mc Inerney 2 Richard Nowakowski 3 Melissa Huggan 3
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We introduce the Orthogonal Colouring Game, in which two players alternately colour vertices (from a choice of m ∈ N colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the colouring. Each player aims to maximise her score, which is the number of coloured vertices in the copy of the graph she owns. The main result of this paper is that the second player has a strategy to force a draw in this game for any m ∈ N for graphs that admit a strictly matched involution. An involution σ of a graph G is strictly matched if its fixed point set induces a clique and any non-fixed point v ∈ V (G) is connected with its image σ(v) by an edge. We give a structural characterisation of graphs admitting a strictly matched involution and bounds for the number of such graphs. Examples of such graphs are the graphs associated with Latin squares and sudoku squares.
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-02017462
Contributor : Fionn Mc Inerney <>
Submitted on : Friday, March 1, 2019 - 2:52:31 PM
Last modification on : Tuesday, March 5, 2019 - 1:41:04 AM
Long-term archiving on : Thursday, May 30, 2019 - 3:13:45 PM

File

final76orthogonalGraphColoring...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02017462, version 2

Citation

Stephan Dominique Andres, Fionn Mc Inerney, Richard Nowakowski, Melissa Huggan. The Orthogonal Colouring Game. [Research Report] Inria - Sophia Antipolis. 2019. ⟨hal-02017462v2⟩

Share

Metrics

Record views

50

Files downloads

59