<p>I can prove that no 4-regular graphs are 3-acyclic colorable.</p>
<p>Consider a 4-regular graph with a 3-coloring. If we call the colors <span class="math-container">$a, b, c$</span>, then one of the three subgraphs generated by restricting to either <span class="math-container">$a$</span> and <span class="math-container">$b$</span> colored vertices, <span class="math-container">$a$</span> and <span class="math-container">$c$</span> vcertices, or <span class="math-container">$b$</span> and <span class="math-container">$c$</span> vertices must have as many edges as vertices. But all graphs with as many edges as vertices contain a cycle, so the coloring is not acyclic.</p>
<p>Let the graph have <span class="math-container">$k$</span> vertices. The graph must have <span class="math-container">$2k$</span> edges, because it is 4-regular. Let the number of <span class="math-container">$a$</span> colored vertices be <span class="math-container">$k_a$</span>, and similarly for <span class="math-container">$k_b$</span> and <span class="math-container">$k_c$</span>. Call <span class="math-container">$e_{ab}$</span> the number of edges between <span class="math-container">$a$</span> and <span class="math-container">$b$</span> colored vertices, and the same for <span class="math-container">$e_{ac}$</span> and <span class="math-container">$e_{bc}$</span>. If we assume that none of the restricted graphs have as many edges as vertices, we must have
<span class="math-container">$$
e_{ab} &lt; k_a + k_b, \\
e_{ac} &lt; k_a + k_c, \\
e_{bc} &lt; k_b + k_c \\
$$</span>
Summing over all edges, we find that <span class="math-container">$e_{ab} + e_{ac} + e_{bc} &lt; 2(k_a + k_b + k_c)$</span>, and so <span class="math-container">$e &lt; 2k$</span>. But this contradicts the fact that 4-regular graphs have twice as many edges as vertices, mentioned above. Thus, the assumption is false, and some color-restricted subgraph has as many edges as vertices, and hence has a cycle.</p>

CC BY-SA 4.0
2020-06-10T04:10:40.887Z
Great. Similarly, we can prove that 6-regular graphs are not 4-acyclic colourable.
Cyriac Antony
CC BY-SA 4.0
2020-06-10T04:13:55.973Z
In general, $2k$-regular graphs are not $(k+1)$-acyclic colourable.
Cyriac Antony
CC BY-SA 4.0
2020-07-12T04:58:23.293Z
I would like to cite this answer (in the usual way). How should I give your name: Is it Issac G. ? (full name would be preferable).
Cyriac Antony
CC BY-SA 4.0
2020-07-12T17:07:31.670Z
@CyriacAntony My name is Isaac Grosof.
isaacg
CC BY-SA 4.0
2020-11-17T05:34:52.360Z
Sorry, earlier I couldn't find it in the literature. But, the lower bound given by your answer (i.e. $\chi_a(G)\geq (d+3)/2$) is also a direct consequence of Proposition 1 in Fertin et al., [Acyclic and $k$-distance coloring of the grid](https://doi.org/10.1016/S0020-0190(03)00232-1). But, your proof is more beautiful.
Cyriac Antony
CC BY-SA 4.0
2020-06-09T18:44:29.830Z
2024-07-15T19:20:59.400Z
2024-07-15T19:20:59.400Z
isaacg
<p>A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours).</p>

<p>Burstein proved that 4-regular graphs are 5-acyclic colourable. <strong>It seems to me that no planar 4-regular graph is 3-acyclic colourable</strong> (might be even true for 4-regular graphs in general).</p>

<p>Am I wrong?<br>
Is this already studied? (I admit I couldn't find any).</p>

CC BY-SA 4.0
2020-06-09T06:44:37.707Z
By the way, is there an English translation of Burstein's paper? (original is in Russian)
Cyriac Antony
CC BY-SA 4.0
2020-06-09T14:25:57.610Z
So your question is whether there is a 4-regular (planar) graph such that we can PROPERLY 3-color its VERTICES such that every cycles gets all 3 colors.
domotorp
CC BY-SA 4.0
2020-06-09T16:58:37.987Z
@domotorp Exactly
Cyriac Antony
CC BY-SA 4.0
2020-06-09T18:37:34.117Z
It's possible to 3-color the rhombicuboctahedron so that every face has all three colors. But that doesn't answer your question because there might be non-face cycles that are still only 2-colored.
David Eppstein
<graph-theory><planar-graphs><graph-colouring>
Is there a planar 4-regular graph that is 3-acyclic colourable?
Cyriac Antony
# Is there a planar 4-regular graph that is 3-acyclic colourable?

(Asked by: username_0 on 2020-06-09)

A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours).

Burstein proved that 4-regular graphs are 5-acyclic colourable. **It seems to me that no planar 4-regular graph is 3-acyclic colourable** (might be even true for 4-regular graphs in general).

Am I wrong?  
Is this already studied? (I admit I couldn't find any).

**Tags:** graph-theory, planar-graphs, graph-colouring

> **Comments:**
> **username_0**: By the way, is there an English translation of Burstein's paper? (original is in Russian)  
> **username_1**: So your question is whether there is a 4-regular (planar) graph such that we can PROPERLY 3-color its VERTICES such that every cycles gets all 3 colors.  
> **username_0**: @username_1 Exactly  
> **username_2**: It's possible to 3-color the rhombicuboctahedron so that every face has all three colors. But that doesn't answer your question because there might be non-face cycles that are still only 2-colored.  

---

## 1 answers

### Answer by username_3 on 2020-06-09. Score: 13 | Accepted answer

I can prove that no 4-regular graphs are 3-acyclic colorable.

Consider a 4-regular graph with a 3-coloring. If we call the colors $a, b, c$, then one of the three subgraphs generated by restricting to either $a$ and $b$ colored vertices, $a$ and $c$ vcertices, or $b$ and $c$ vertices must have as many edges as vertices. But all graphs with as many edges as vertices contain a cycle, so the coloring is not acyclic.

Let the graph have $k$ vertices. The graph must have $2k$ edges, because it is 4-regular. Let the number of $a$ colored vertices be $k\_a$, and similarly for $k\_b$ and $k\_c$. Call $e\_{ab}$ the number of edges between $a$ and $b$ colored vertices, and the same for $e\_{ac}$ and $e\_{bc}$. If we assume that none of the restricted graphs have as many edges as vertices, we must have
$$
e\_{ab} < k\_a + k\_b, \\
e\_{ac} < k\_a + k\_c, \\
e\_{bc} < k\_b + k\_c \\
$$
Summing over all edges, we find that $e\_{ab} + e\_{ac} + e\_{bc} < 2(k\_a + k\_b + k\_c)$, and so $e < 2k$. But this contradicts the fact that 4-regular graphs have twice as many edges as vertices, mentioned above. Thus, the assumption is false, and some color-restricted subgraph has as many edges as vertices, and hence has a cycle.

> **Comments:**
> **username_0**: Great. Similarly, we can prove that 6-regular graphs are not 4-acyclic colourable.  
> **username_0**: In general, $2k$-regular graphs are not $(k+1)$-acyclic colourable.  
> **username_0**: I would like to cite this answer (in the usual way). How should I give your name: Is it Issac G. ? (full name would be preferable).  
> **username_3**: @CyriacAntony My name is Isaac Grosof.  
> **username_0**: Sorry, earlier I couldn't find it in the literature. But, the lower bound given by your answer (i.e. $\chi_a(G)\geq (d+3)/2$) is also a direct consequence of Proposition 1 in Fertin et al., [Acyclic and $k$-distance coloring of the grid](https://doi.org/10.1016/S0020-0190(03)00232-1). But, your proof is more beautiful.  

---

