|
This article is cited in 1 scientific paper (total in 1 paper)
Estimating the Minimal Number of Colors in Acyclic -Strong Colorings of Maps on Surfaces
O. V. Borodina, A. V. Kostochkaa, A. Raspaudb, E. Sopenab a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b Université Bordeaux 1
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\ge 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\ge 1$ and $-N\ge 5^7k^{4/3}$.
Received: 29.08.2001
Citation:
O. V. Borodin, A. V. Kostochka, A. Raspaud, E. Sopena, “Estimating the Minimal Number of Colors in Acyclic -Strong Colorings of Maps on Surfaces”, Mat. Zametki, 72:1 (2002), 35–37; Math. Notes, 72:1 (2002), 31–42
Linking options:
https://www.mathnet.ru/eng/mzm401https://doi.org/10.4213/mzm401 https://www.mathnet.ru/eng/mzm/v72/i1/p35
|
|