Acyclic k-strong coloring of maps on surfaces.

A coloring of graph vertices 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 not greater than k, k ≥ 4, on a surface S ^N is replaced by the clique on the same set of vertices. Then the pseudograph obtained in this way can be colored acyclically in a set of colors whose cardinality depends linearly on N and on k. Results of this kind were known before only for 1 ≤ N ≤ 2 and 3 ≤ k ≤ 4. [ABSTRACT FROM AUTHOR]