Complexity Classification of Colouring Problems with Parity Constraints

Rémy Belmonte, Juan Pablo Bravo, Noleen Köhler +1

We study variants of graph colouring with parity constraints. More specifically, we consider $q$-colourings $c:V(G)\to \{1,\dots ,q\}$ of a graph $G$ where, for every…