{"id":"arxiv/2606.21534","url":"https://arxiv.org/abs/2606.21534","tags":["math.CO","cs.CC"],"score":0,"title":"Conformability is NP-complete, even on connected regular graphs","domain":"math.CO","source":"arxiv","authors":["József Pintér"],"reviews":0,"subject":"math.CO","summary":"A graph $G$ is conformable if it admits a proper $(Δ(G)+1)$-coloring in which, among the $Δ(G)+1$ color classes including the empty ones, at most $\\sum_{v\\in V(G)}(Δ(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 problem by proving that Conformability is NP-complete. Hardness holds even for connected regular graphs $G$ of odd order with independence number $α(G)=3$ and maximum…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-19","reactions":{}}