Acyclic \(k\)-strong coloring of maps on surfaces (Q1581455)

A proper vertex-coloring of a graph is said to be acyclic if there are no two-colored cycles. The authors show that, if each face having size at most \(k\) (where \(k\geq 4\)) of a graph imbedding on a surface of characteristic \(N\) is replaced by a clique on the same vertex set, then the resulting pseudograph has an acyclic vertex-coloring of cardinality depending linearly on \(N\) and \(k\). Previously, such results were known only for \(N= 1\) or \(2\), and \(k= 3\) or \(4\).