"The complexity of graph Ramsey games"


Wolfgang Slany
Technische Universitaet Wien, Austria


Given two graphs G and A, two players, Red and Green, alternate in
coloring the edges of G in their respective colors. Their goal is to avoid
building a monochromatic subgraph isomorphic to A. In another variant, 
their goal is to build a monochromatic subgraph isomorphic to A. I determine
the computational complexity of finding winning strategies for several
variants of these games.

A Java applet that improves its strategy by playing over the Internet and
that allows to play some small but nontrivial instances can be challenged
at http://www.dbai.tuwien.ac.at/proj/ramsey/. Please try it out! In case
you win, you will be able to leave your name in our hall-of-fame.



CS seminar, October 25, 1999.