no. 16 · Tuesday 17 November 2026
Planar PArcK is PSPACE-complete
Abstract
Partizan Arc Kayles, or PArcK, is a partizan combinatorial game on edge colored graphs, and is a generalization of the game Domineering. Previously, PArcK was shown to be PSPACE-complete on bipartite graphs. In this paper we show that PArcK is PSPACE-complete even when restricted to planar graphs of degree at most three by a reduction from Generalized Hex.
- comments
- 9 pages
- fields
- Combinatorics