Showing cs.CCShow all
3 papers · 1 filter
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…
cs.CC2025
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…