The Curious Case of Col's Computational Complexity
Kyle (noreply@blogger.com)
Col is one of three basic placement games on graphs along with Snort and Node Kayles . In all three, players take turns painting vertices their color, with a restriction based on what colors are neighboring. In Col, you can't paint a vertex adjacent to another vertex that already has your color. In Snort, you can't paint adjacent to a vertex in your opponent's color. In Node Kayles, you can't paint adjacent to either color. (That's not usually how Node Kayles is described, but this is equiv