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 language | English (US) |
---|---|
Pages (from-to) | 31-33 |
Number of pages | 3 |
Journal | Mathematical Notes |
Volume | 72 |
Issue number | 1-2 |
DOIs | |
State | Published - 2002 |
Externally published | Yes |
Keywords
- Acyclic colorings
- Graphs on surfaces
- K-strong colorings
ASJC Scopus subject areas
- General Mathematics