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.
