<p>All graphs in this question are finite, simple and undirected.
Let <span class="math-container">$k$</span> be a fixed positive integer.</p>
<p>A <span class="math-container">$k$</span>-colouring of a graph <span class="math-container">$G$</span> is a function <span class="math-container">$f\colon V(G)\to\{1,2,\dots,k\}$</span> such that <span class="math-container">$f(u)\neq f(v)$</span> for every edge <span class="math-container">$xy$</span> of <span class="math-container">$G$</span>. A <span class="math-container">$k$</span>-colouring of <span class="math-container">$G$</span> is a <em><span class="math-container">$k$</span>-acyclic colouring</em> of <span class="math-container">$G$</span> if there is no cycle in <span class="math-container">$G$</span> bicoloured by <span class="math-container">$f$</span> (i.e., coloured using only 2 colours under <span class="math-container">$f$</span>).</p>
<p>The problem <span class="math-container">$k$</span>-COLOURABILITY takes a graph <span class="math-container">$G$</span> as input and asks whether <span class="math-container">$G$</span> is <span class="math-container">$k$</span>-colourable. The problem <span class="math-container">$k$</span>-ACYCLIC COLOURABILITY takes a graph <span class="math-container">$G$</span> as input and asks whether <span class="math-container">$G$</span> is <span class="math-container">$k$</span>-acyclic colourable.</p>
<p>To read about Constraint Satisfaction Problem (CSP), see [1] (for instance).</p>
<p>It is well-known that <span class="math-container">$k$</span>-COLOURABILITY is in CSP (for example, by homomorphism definition of k-colouring).<br />
<strong>Is k-ACYCLIC COLOURABLITY in CSP?</strong></p>
<p><em>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.</em><br />
PS: I am a newbie in CSP and MMSNP; feel free to correct me if I am wrong about these.</p>
<p>For comparison, let us consider two special cases of acyclic colouring (I mean acyclic colouring with extra conditions). A <span class="math-container">$k$</span>-colouring of <span class="math-container">$G$</span> is a <span class="math-container">$k$</span>-star colouring of <span class="math-container">$G$</span> if there is no bicoloured 4-vertex path in <span class="math-container">$G$</span> bicoloured by <span class="math-container">$f$</span>. A distance-two <span class="math-container">$k$</span>-colouring of <span class="math-container">$G$</span> is a <span class="math-container">$k$</span>-colouring of <span class="math-container">$G$</span> such that <span class="math-container">$f(u)\neq f(v)$</span> for every pair of vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span> in <span class="math-container">$G$</span> within distance two (i.e., <span class="math-container">$uv$</span> is an edge, or <span class="math-container">$u$</span> and <span class="math-container">$v$</span> have a common neighbour). The problems <span class="math-container">$k$</span>-STAR COLOURABILITY and DISTANCE-TWO <span class="math-container">$k$</span>-COLOURABILITY are defined in the obvious way.<br />
It is easy to see that <span class="math-container">$k$</span>-STAR COLOURABILITY and DISTANCE-TWO <span class="math-container">$k$</span>-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.</p>
<p>[1] <em>Bulatov, Andrei A.</em>, <a href="http://dx.doi.org/10.1007/978-3-319-77313-1_1" rel="nofollow noreferrer"><strong>Constraint satisfaction problems: complexity and algorithms</strong></a>,  <a href="https://zbmath.org/?q=an:06894736" rel="nofollow noreferrer">ZBL06894736</a>.</p>

CC BY-SA 4.0
2022-05-04T07:57:54.217Z
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 ...
Emil Jeřábek
CC BY-SA 4.0
2022-05-04T07:58:20.667Z
... vertices of the line, creating a $2$-coloured cycle.
Emil Jeřábek
CC BY-SA 4.0
2022-05-04T08:46:04.493Z
@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.
Cyriac Antony
CC BY-SA 4.0
2022-05-04T08:59:44.403Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-05-04T10:07:29.443Z
@EmilJeřábek "A homomorphism can only go between two structures of the same signature". True. But, a graph theoretic problem can be expressed with signature other than $<V,E>$. E.g.: graph isomorphism from $G(V,E)$ to $H(W,F)$ is a homomorphsim from $<V,E,E'>$ to $<W,F,F'>$ where $E'=V^2\setminus E$ and $F'=W^2\setminus F$.
Cyriac Antony
CC BY-SA 4.0
2022-05-04T10:11:26.153Z
Define what exactly you mean by “express”, then. In a fairly reasonable sense, *every* NP-complete problem can be “expressed” by a CSP, as it is poly-time equivalent e.g. to 3-colourability.
Emil Jeřábek
CC BY-SA 4.0
2022-05-04T10:14:51.030Z
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).
Emil Jeřábek
<cc.complexity-theory><graph-theory><csp>
Is k-ACYCLIC COLOURABLITY in CSP?
Cyriac Antony
# Is k-ACYCLIC COLOURABLITY in CSP?

(Asked by: username_0 on 2022-05-04)

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).  
**Is k-ACYCLIC COLOURABLITY in CSP?**

*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**](http://dx.doi.org/10.1007/978-3-319-77313-1_1), [ZBL06894736](https://zbmath.org/?q=an:06894736).

**Tags:** cc.complexity-theory, graph-theory, csp
> **Comments:**
> **username_1**: 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 ...  
> **username_1**: ... vertices of the line, creating a $2$-coloured cycle.  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_0**: @EmilJeřábek "A homomorphism can only go between two structures of the same signature". True. But, a graph theoretic problem can be expressed with signature other than $<V,E>$. E.g.: graph isomorphism from $G(V,E)$ to $H(W,F)$ is a homomorphsim from $<V,E,E'>$ to $<W,F,F'>$ where $E'=V^2\setminus E$ and $F'=W^2\setminus F$.  
> **username_1**: Define what exactly you mean by “express”, then. In a fairly reasonable sense, *every* NP-complete problem can be “expressed” by a CSP, as it is poly-time equivalent e.g. to 3-colourability.  
> **username_1**: 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).  

---

## 0 answers

