Paperlane

no. 16 · Tuesday 17 November 2026

Planar PArcK is PSPACE-complete

Craig Tennenhouse and Kanae Yoshiwatari

math.CO · via cs.CC · 9 pp

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
pdf ↗ page arXiv:2611.20138 ↗