A Symmetric Strategy in Graph Avoidance Games

Details A Symmetric Strategy in Graph Avoidance Games A Symmetric Strategy in Graph Avoidance Games

2001-10-24

arxiv.org/abs/cs/0110049v1

Computer Science

Discrete Mathematics

14 pages, 6 figures; for a video of a talk based on a preliminary version see http://www.msri.org/publications/ln/msri/2000/

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Symmetric Strategy in Graph Avoidance Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Symmetric Strategy in Graph Avoidance Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Symmetric Strategy in Graph Avoidance Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-650945