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 
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/
@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},
     year = {2002},
     volume = {72},
     number = {1},
     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
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
%U http://geodesic.mathdoc.fr/item/MZM_2002_72_1_a2/
%G ru
%F MZM_2002_72_1_a2

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}$.

[1] Borodin O. V., Kostochka A. V., Raspo A., Sopena E., “Atsiklicheskaya $k$-silnaya raskraska kart na poverkhnostyakh”, Matem. zametki, 67:1 (2000), 36–45 | MR | Zbl

[2] Alon N., Marshall T. H., “Homomorphisms of edge-colored graphs and Coxeter groups”, J. Algebraic Combinatorics, 2 (1998), 277–289

[3] Grünbaum B., “Acyclic colorings of planar graphs”, Israel J. Math., 14:3 (1973), 390–408 | DOI | MR | Zbl

[4] Jensen T. R., Toft B., Graph Coloring Problems, Wiley, New York, 1995

[5] Nešetřil J., Raspaud A., Colored Homomorphisms of Colored Mixed Graphs, KAM Series No. 98-376, Dept. Applied Math., Charles University, 1998

[6] Raspaud A., Sopena E., “Good and semi-strong colorings of oriented planar graphs”, Inform. Processing Letters, 51 (1994), 171–174 | DOI | MR | Zbl

[7] Alon N., Mohar B., Sanders D. P., “On acyclic colorings of graphs on surfaces”, Israel J. Math., 94 (1996), 273–283 | DOI | MR | Zbl

[8] Alon N., McDiarmid C., Reed B., “Acyclic colorings of graphs”, Random Struct. Algorithms, 2 (1991), 277–288 | MR | Zbl