Conformability is NP-complete, even on connected regular graphs (opens in new tab)

A graph $G$ is conformable if it admits a proper $(\Delta(G)+1)$-coloring in which, among the $\Delta(G)+1$ color classes including the empty ones, at most $\sum_{v\in V(G)}(\Delta(G)-d_G(v))$ have parity different from that of $|V(G)|$. The complexity of deciding conformability was left open in recent work, and positive results for several graph classes had suggested that the problem might be polynomial-time solvable. We settle the general pr...