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$ – Cyriac Antony Jun 9 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 Jun 9 at 14:25
  • $\begingroup$ @domotorp Exactly $\endgroup$ – Cyriac Antony Jun 9 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$ – David Eppstein Jun 9 at 18:37

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.

| cite | improve this answer | |
  • $\begingroup$ Great. Similarly, we can prove that 6-regular graphs are not 4-acyclic colourable. $\endgroup$ – Cyriac Antony Jun 10 at 4:10
  • 2
    $\begingroup$ In general, $2k$-regular graphs are not $(k+1)$-acyclic colourable. $\endgroup$ – Cyriac Antony Jun 10 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$ – Cyriac Antony Jul 12 at 4:58
  • $\begingroup$ @CyriacAntony My name is Isaac Grosof. $\endgroup$ – isaacg Jul 12 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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