Geodesic
Estimating the Minimal Number of Colors in Acyclic -Strong Colorings of Maps on Surfaces
Matematičeskie zametki, Tome 72 (2002) no. 1, pp. 35-37

Voir la notice de l'article provenant de la source Math-Net.Ru

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}$. 
@article{MZM_2002_72_1_a2,
     author = {O. V. Borodin and A. V. Kostochka and A. Raspaud and E. Sopena},
     title = {Estimating the {Minimal} {Number} of {Colors} in {Acyclic}  {-Strong} {Colorings} of {Maps} on {Surfaces}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {35--37},
     publisher = {mathdoc},
     volume = {72},
     number = {1},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2002_72_1_a2/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. V. Kostochka
AU  - A. Raspaud
AU  - E. Sopena
TI  - Estimating the Minimal Number of Colors in Acyclic  -Strong Colorings of Maps on Surfaces
JO  - Matematičeskie zametki
PY  - 2002
SP  - 35
EP  - 37
VL  - 72
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2002_72_1_a2/
LA  - ru
ID  - MZM_2002_72_1_a2
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. V. Kostochka
%A A. Raspaud
%A E. Sopena
%T Estimating the Minimal Number of Colors in Acyclic  -Strong Colorings of Maps on Surfaces
%J Matematičeskie zametki
%D 2002
%P 35-37
%V 72
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2002_72_1_a2/
%G ru
%F MZM_2002_72_1_a2
O. V. Borodin; A. V. Kostochka; A. Raspaud; E. Sopena. Estimating the Minimal Number of Colors in Acyclic  -Strong Colorings of Maps on Surfaces. Matematičeskie zametki, Tome 72 (2002) no. 1, pp. 35-37. http://geodesic.mathdoc.fr/item/MZM_2002_72_1_a2/