Portal de Periódicos da CAPES

Acyclick-strong coloring of maps on surfaces

2000; Pleiades Publishing; Volume: 67; Issue: 1 Linguagem: Inglês

10.1007/bf02675788

1573-8876

O. V. Borodin, Alexandr Kostochka, André Raspaud, Éric Sopena,

Graph Labeling and Dimension Problems

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 thank, k ≥ 4, on a surfaceS 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 onN and onk. Results of this kind were known before only for 1 ≤N ≤ 2 and 3 ≤k ≤ 4.