PSPACE-completeness conjecture for symmetric binary graph Ramsey avoidance games

About 27 years old · traced to

Let KkK_k and KnK_n be complete graphs, let ErE^r and EgE^g be precolored red and green edge sets, and let Ramsey(n,n)\mathrm{Ramsey}(n,n) denote the classic symmetric binary Ramsey number. Classic Ramsey-number avoidance conjecture. Graph Ramsey avoidance games played on (Kk,Kn,Er,Eg)(K_k,K_n,E^r,E^g) where k≥Ramsey(n,n)k\geq\mathrm{Ramsey}(n,n) are PSPACE{\bf PSPACE}-complete. The conjecture restricts avoidance games to complete host graphs whose order is at least the corresponding symmetric binary Ramsey number; the paper presents these games as difficult, but supplies no resolution of the conjecture.

References

Primary source

Wolfgang Slany, “Graph Ramsey games”, arXiv:cs/9911004 (1999).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.