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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-10 Page: https://delphi.science/r/arxiv/2607.09631 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.