{"id":"arxiv/2607.09631","url":"https://arxiv.org/abs/2607.09631","tags":["math.CO","cs.CC"],"score":0,"title":"Cut-homotopies and the complexity of edge-coloring problems","domain":"math.CO","source":"arxiv","authors":["Alexey Barsukov","Roman Feller","Maximilian Hadek","Davide Perinti"],"reviews":0,"subject":"math.CO","summary":"We study the computational complexity of problems that ask if a given graph admits an edge-coloring that does not contain an edge-colored clique from some fixed finite family. We show that every such problem is poly-time equivalent to a Constraint Satisfaction Problem, yielding a P vs. NP-complete dichotomy. Our main contribution lies in the reduction from the CSP to the coloring problem where we apply methods from Ramsey theory and a novel notion of cut-homotopy.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}