By MMSNP, I mean Monotone Monadic SNP without inequality. For $k\in\mathbb{N}$, the problem $k$-COLOURABILITY takes a graph $G$ as input and asks whether $G$ is $k$-colourable. It is well-known that for every $k\in\mathbb{N}$, $k$-COLOURABILITY is a finite-domain Constraint Satisfaction Problem (CSP). Does this suggest that there is an MMSNP formula for $k$-COLOURABILITY?

Is there an MMSNP formula for 3-COLOURABILITY?

It seems to me that the monotone condition makes it difficult to express that $\{V_1,V_2,V_3\}$ is a partition of the vertex set.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.