Advertisement
Published in:
01-05-2015
The \(r\)-acyclic chromatic number of planar graphs
Published in: Journal of Combinatorial Optimization | Issue 4/2015
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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.