{"id":"arxiv/2607.16879","url":"https://arxiv.org/abs/2607.16879","tags":["cs.DS","math.CO"],"score":0,"title":"Complexity Classification of Colouring Problems with Parity Constraints","domain":"cs.DS","source":"arxiv","authors":["Rémy Belmonte","Juan Pablo Bravo","Noleen Köhler","Haiko Müller"],"reviews":0,"subject":"cs.DS","summary":"We study variants of graph colouring with parity constraints. More specifically, we consider $q$-colourings $c\\colon V(G)\\rightarrow \\{1,\\dots,q\\}$ of a graph $G$ where, for every vertex $v\\in V(G)$, the number of neighbours $w$ of $v$ with $c(w)=c(v)$ is restricted to be odd, even, positive, zero or a combination thereof. For every colour $i\\neq c(v)$ the number of neighbours $w$ of $v$ with $c(w)=i$ is restricted by a constraint of similar type. Many known colouring problems such as proper colouring, defective colouring, exact defective colouring, odd colouring, and strong odd colouring…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-18","reactions":{}}