Estimating the Minimal Number of Colors in Acyclic -Strong Colorings of Maps on Surfaces

O. V. Borodin ; A. V. Kostochka ; A. Raspaud ; E. Sopena

Matematičeskie zametki, Tome 72 (2002) no. 1, pp. 35-37

Résumé

A coloring of the vertices of a graph is called acyclic if the ends of each edge are colored in distinct colors, and there are no two-colored cycles. Suppose each face of rank $k$, $k\ge 4$, in a map on a surface $S^N$ is replaced by the clique having the same number of vertices. It is proved in [1] that the resulting pseudograph admits an acyclic coloring with the number of colors depending linearly on $N$ and $k$. In the present paper we prove a sharper estimate $55(-Nk)^{4/7}$ for the number of colors provided that $k\ge 1$ and $-N\ge 5^7k^{4/3}$.