Estimating the minimal number of colors in acyclic k-strong colorings of maps on surfaces

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 ≥ 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 ≥ 1 and N ≥ 5 ⁷k ^4/3.