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

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

Research output: Contribution to journalArticlepeer-review

Abstract

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 7k 4/3.

Original languageEnglish (US)
Pages (from-to)31-33
Number of pages3
JournalMathematical Notes
Volume72
Issue number1-2
DOIs
StatePublished - 2002
Externally publishedYes

Keywords

  • Acyclic colorings
  • Graphs on surfaces
  • K-strong colorings

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Estimating the minimal number of colors in acyclic k-strong colorings of maps on surfaces'. Together they form a unique fingerprint.

Cite this