Cut-homotopies and the complexity of edge-coloring problems

Alexey Barsukov, Roman Feller, Maximilian Hadek +1

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 s…