Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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).
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.
