Showing 2026Show all
3 papers · 1 filter
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
Towards infinite PCSP: a dichotomy for monochromatic cliques
Demian Banakh, Alexey Barsukov, Tamio-Vesa Nakajima
The logic MMSNP is a well-studied fragment of Existential Second-Order logic that, from a computational perspective, captures finite-domain Constraint Satisfaction Problems (CSPs)…
cs.CC2026
On the complexity of Sandwich Problems for -partitions
Alexey Barsukov, Santiago Guzmán-Pro
We present a structural classification of constraint satisfaction problems (CSP) described by reflexive complete -edge-coloured graphs. In particular, this classification extend…