zbMATH — the first resource for mathematics

Acyclic coloring of 1-planar graphs. (Russian) Zbl 0931.05032
A graph is said to be 1-planar if it can be embedded into the plane so that each of its edges is crossed by at most one other edge. A coloring of the vertices of a graph is said to be acyclic if every cycle contains at least three colors. The acyclic chromatic number \(a(G)\) of a graph \(G\) is the minimal \(k\) such that \(G\) admits an acyclic \(k\)-coloring. O. Borodin [Discrete Math. 25, No. 3, 211-236 (1979; Zbl 0406.05031)] proved the conjecture of Grünbaum that every planar graph is acyclically 5-colorable. The main result of the article under review states that every 1-planar graph can be colored in 20 colors. Note that the largest known value among the acyclic chromatic numbers of 1-planar graphs is 7.

05C15 Coloring of graphs and hypergraphs