Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.

DOI10.1016/S0304-3975(01)00179-7MaRDI QIDQ1853560zbMATH OpenFDO

Authors Wolfgang Slany

Publication date 21 January 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00179-7

zbMATH Keywords

avoidance gamescomplexity theoryedge coloringgeneralized Ramsey theorygraph Ramsey theoryPSPACE-completenessSim

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Games involving graphs (91A43)

Recommendations

• Graph Ramsey games
• scientific article; zbMATH DE number 139777
• scientific article; zbMATH DE number 3900800
• ON THE COMPLEXITY OF SOME COLORING GAMES
• PSPACE-Hardness of some combinatorial games

Cites work

• A Combinatorial Problem Which Is Complete in Polynomial Space
• Alternation
• Combinatorial Relations and Chromatic Graphs
• Games against nature
• Generalized Ramsey theory for graphs
• GO Is Polynomial-Space Hard
• Gobang is PSPACE-complete
• Graph Ramsey games
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• scientific article; zbMATH DE number 5145333 (Why is no real title available?)
• scientific article; zbMATH DE number 3470438 (Why is no real title available?)
• scientific article; zbMATH DE number 3487493 (Why is no real title available?)
• scientific article; zbMATH DE number 1236365 (Why is no real title available?)
• On a combinatorial game
• On the complexity of some two-person perfect-information games
• Playing disjunctive sums is polynomial space complete
• Small Ramsey numbers
• Subgraph counting identities and Ramsey numbers
• The Othello game on an \(n\times n\) board is PSPACE-complete
• The Pebbling Problem is Complete in Polynomial Space

Cited in

(4)

• Graph Ramsey games
• Avoidance game on Steiner triple systems
• The general position avoidance game and hardness of general position games
• 6-uniform maker-breaker game is PSPACE-complete

This page was built for publication: Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853560)