# Is there a planar 4-regular graph that is 3-acyclic colourable?

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?

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

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.
• In general, $2k$-regular graphs are not $(k+1)$-acyclic colourable. – Cyriac Antony Jun 10 '20 at 4:13
• 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. – Cyriac Antony Nov 17 '20 at 5:34