Acyclic k-strong coloring of maps on surfaces

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

Research output: Contribution to journalArticlepeer-review


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 SN 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.

Original languageEnglish (US)
Pages (from-to)29-35
Number of pages7
JournalMathematical Notes
Issue number1
StatePublished - 2000
Externally publishedYes


  • Acyclic coloring
  • Acyclic graphs
  • Cliques
  • Embedded graphs
  • Map coloring

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Acyclic k-strong coloring of maps on surfaces'. Together they form a unique fingerprint.

Cite this