2001/10/24 by Frank Harary, Harary, Frank, Wolfgang Slany +3 · 1 citation
Computer Science · Decision Sciences · #Advanced Graph Theory Research #Artificial Intelligence in Games #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.1.3 #FOS: Computer and information sciences #G.2.1 #G.2.2 #Game Theory and Applications #cs.CC #cs.DM
paper · pdf · doi:10.48550/arxiv.cs/0110049
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/
arxiv created 2001/10/24 · openalex publication_date 2001/10/24 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.