Col is PSPACE-complete on Triangular Grids
arXiv:2501.06574
Abstract
We demonstrate that Col is PSPACE-complete on triangular grid graphs via a reduction from Bounded Two-Player Constraint Logic. This is the most structured graph family that Col is known to be computationally hard for.
10 pages, 16 figures