Name
Abstract | ||
|---|---|---|
In the graph avoidance game two players alternately color the edges of a graph G in red and in blue respectively. The player who rst creates a monochromatic subgraph isomorphic to a forbidden graph F loses. A symmetric strategy of the second player ensures that, independently of the rst 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. |
Year | Venue | Keywords |
|---|---|---|
2001 | Clinical Orthopaedics and Related Research | computational complexity,discrete mathematics |
Field | DocType | Volume |
Discrete mathematics,Vertex-transitive graph,Line graph,Graph factorization,Foster graph,Symmetric game,Symmetric graph,Butterfly graph,Mathematics,Voltage graph | Journal | cs.DM/0110 |
Citations | PageRank | References |
3 | 0.68 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank Harary | 1 | 907 | 270.87 |
| Wolfgang Slany | 2 | 329 | 49.70 |
| Oleg Verbitsky | 3 | 191 | 27.50 |