All graphs in this question are finite, simple and undirected. Let $k$ be a fixed positive integer.

A $k$-colouring of a graph $G$ is a function $f\colon V(G)\to\{1,2,\dots,k\}$ such that $f(u)\neq f(v)$ for every edge $xy$ of $G$. A $k$-colouring of $G$ is a $k$-acyclic colouring of $G$ if there is no cycle in $G$ bicoloured by $f$ (i.e., coloured using only 2 colours under $f$).

The problem $k$-COLOURABILITY takes a graph $G$ as input and asks whether $G$ is $k$-colourable. The problem $k$-ACYCLIC COLOURABILITY takes a graph $G$ as input and asks whether $G$ is $k$-acyclic colourable.

To read about Constraint Satisfaction Problem (CSP), see [1] (for instance).

It is well-known that $k$-COLOURABILITY is in CSP (for example, by homomorphism definition of k-colouring).

I don't see a direct way to express k-ACYCLIC COLOURABLITY as a CSP. Also, the 'natural' MSO formulas for k-ACYCLIC COLOURABLITY are not MMSNP formulas.
PS: I am a newbie in CSP and MMSNP; feel free to correct me if I am wrong about these.

For comparison, let us consider two special cases of acyclic colouring (I mean acyclic colouring with extra conditions). A $k$-colouring of $G$ is a $k$-star colouring of $G$ if there is no bicoloured 4-vertex path in $G$ bicoloured by $f$. A distance-two $k$-colouring of $G$ is a $k$-colouring of $G$ such that $f(u)\neq f(v)$ for every pair of vertices $u$ and $v$ in $G$ within distance two (i.e., $uv$ is an edge, or $u$ and $v$ have a common neighbour). The problems $k$-STAR COLOURABILITY and DISTANCE-TWO $k$-COLOURABILITY are defined in the obvious way.
It is easy to see that $k$-STAR COLOURABILITY and DISTANCE-TWO $k$-COLOURABILITY are in CSP. This can be proved using the conventional definition of CSP (as opposed to the homomorphism definition of CSP). Alternatively, it is easy to see that the natural MSO formulas for these problems are MMSNP formulas as well.

[1] Bulatov, Andrei A., Constraint satisfaction problems: complexity and algorithms, ZBL06894736.

  • $\begingroup$ This is not my area so I may be misinterpreting something, but it seems to me that the problem cannot be expressed as a (finite) CSP, as there are arbitrarily large $k$-acyclic-colourable graphs that have no homomorphism to a smaller graph with this property. The graphs consist of a $(k-2)$-clique and an (arbitrarily long) line, whose vertices are connected to all vertices of the clique. The only $k$-colourings of this graph assign $k-2$ colours to vertices of the clique, and the remaining two colours alternatively to vertices of the line. Any noninjective homomorphism must identify two ... $\endgroup$ May 4 at 7:57
  • $\begingroup$ ... vertices of the line, creating a $2$-coloured cycle. $\endgroup$ May 4 at 7:58
  • $\begingroup$ @EmilJeřábek But, is graph homomorphism essential? I guess theoretically, it may be possible to express k-ACYCLIC COLOURABILITY as a homomorphism between relational structures with more than one relation (but, I have no idea how to define one, if it is possible). I could be completely off-track here. $\endgroup$ May 4 at 8:46
  • $\begingroup$ A homomorphism can only go between two structures of the same signature, it makes no sense otherwise. You are talking about graphs, hence the signature is given. $\endgroup$ May 4 at 8:59
  • 1
    $\begingroup$ Also, the dichotomy theorem shows that graph isomorphism is not expressible as a CSP in any reasonable way, unless you can show that it is in P (or, even worse, NP-complete). $\endgroup$ May 4 at 10:14


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.