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).

  • $\begingroup$ By the way, is there an English translation of Burstein's paper? (original is in Russian) $\endgroup$ Commented Jun 9, 2020 at 6:44
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Commented Jun 9, 2020 at 14:25
  • $\begingroup$ @domotorp Exactly $\endgroup$ Commented Jun 9, 2020 at 16:58
  • $\begingroup$ 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. $\endgroup$ Commented Jun 9, 2020 at 18:37

1 Answer 1


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.

  • $\begingroup$ Great. Similarly, we can prove that 6-regular graphs are not 4-acyclic colourable. $\endgroup$ Commented Jun 10, 2020 at 4:10
  • 2
    $\begingroup$ In general, $2k$-regular graphs are not $(k+1)$-acyclic colourable. $\endgroup$ Commented Jun 10, 2020 at 4:13
  • $\begingroup$ 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). $\endgroup$ Commented Jul 12, 2020 at 4:58
  • $\begingroup$ @CyriacAntony My name is Isaac Grosof. $\endgroup$
    – isaacg
    Commented Jul 12, 2020 at 17:07
  • $\begingroup$ 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. But, your proof is more beautiful. $\endgroup$ Commented Nov 17, 2020 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.