The \(r\)-acyclic chromatic number of planar graphs
A vertex coloring of a graph G is r-acyclic if it is a proper vertex coloring such that every cycle \(C\) receives at least \(\min \{|C|,r\}\) colors. The \(r\)-acyclic chromatic number \(a_{r}(G)\) of \(G\) is the least number of colors in an \(r\)-acyclic coloring of \(G\). Let \(G\) be a planar graph. By Four Color Theorem, we know that \(a_{1}(G)=a_{2}(G)=\chi (G)\le 4\), where \(\chi (G)\) is the chromatic number of \(G\). Borodin proved that \(a_{3}(G)\le 5\). However when \(r\ge 4\), the \(r\)-acyclic chromatic number of a class of graphs may not be bounded by a constant number. For example, \(a_{4}(K_{2,n})=n+2=\Delta (K_{2,n})+2\) for \(n\ge 2\), where \(K_{2,n}\) is a complete bipartite (planar) graph. In this paper, we give a sufficient condition for \(a_{r}(G)\le r\) when \(G\) is a planar graph. In precise, we show that if \(r\ge 4\) and \(G\) is a planar graph with \(g(G)\ge \frac{10r-4}{3}\), then \(a_{r}(G)\le r\). In addition, we discuss the \(4\)-acyclic colorings of some special planar graphs.
planar graph acyclic coloring girth