Complexity Classification of Colouring Problems with Parity Constraints
Data Structures and Algorithms
Summary
The authors explore different ways to color the nodes of a graph while controlling how neighbors with the same or different colors appear, focusing on whether these neighbor counts are odd, even, zero, or positive. They generalize many existing coloring problems by using these parity-based rules. Their work mainly studies how hard it is to solve these coloring problems with various combinations of such constraints. This provides a unified approach to understanding many known graph coloring challenges.
Authors
Rémy Belmonte, Juan Pablo Bravo, Noleen Köhler, Haiko Müller
Abstract
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 can be described within this framework of constraining graph colourings, and therefore considering variants constitutes a natural generalisation of known colouring problems. We provide a comprehensive study of the computational complexity of different combinations of constraints involving parity.