# 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.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
##### Keywords:
1-planar graph; acyclic coloring