A Symmetric Strategy in Graph Avoidance Games

Harary, Frank; Slany, Wolfgang; Verbitsky, Oleg

A Symmetric Strategy in Graph Avoidance Games

Authors

Harary, Frank

Slany, Wolfgang

Verbitsky, Oleg

Description

In the graph avoidance game two players alternatingly color edges of a graph G in red and in blue respectively. The player who first creates a monochromatic subgraph isomorphic to a forbidden graph F loses. A symmetric strategy of the second player ensures that, independently of the first player's strategy, the blue and the red subgraph are isomorphic after every round of the game. We address the class of those graphs G that admit a symmetric strategy for all F and discuss relevant graph-theoretic and complexity issues. We also show examples when, though a symmetric strategy on G generally does not exist, it is still available for a particular F.
14 pages, 6 figures; for a video of a talk based on a preliminary version see http://www.msri.org/publications/ln/msri/2000/gametheory/slany/1/index.html For related material see http://www.dbai.tuwien.ac.at/proj/ramsey/