2 papers
math.CO2026
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…
cs.CC2026
Edge-coloring problems with forbidden patterns and planted colors
Alexey Barsukov, Antoine Mottet, Davide Perinti
Edge-coloring problems with forbidden patterns are decision problems asking to find an edge-coloring of the input graph which avoids a homomorphism from a fixed forbidden family of…