0
$\begingroup$

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.

$\endgroup$

0

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.