2 papers
cs.CC2025
Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
Kyle Burke, Caroline Cashman, Alfie Davies +2
We show that Misère Partizan Arc Kayles is PSPACE-complete on planar graphs via a reduction from Bounded Two-Player Constraint Logic. Furthermore, we show how to embed our gadgets…
math.CO2025
Structure-biased Maker-Breaker Games
Wesley Pegden, Francesca Yu
In classical Maker-Breaker games on graphs, Maker and Breaker take turns claiming edges; Maker's goal is to claim all of some structure (e.g., a spanning tree, Hamilton cycle, etc.…