文摘
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.