Geodesic
An acyclic analogue to Heawood's theorem
Glasgow mathematical journal, Tome 19 (1978) no. 2, pp. 163-166

Voir la notice de l'article provenant de la source Cambridge University Press

The concept of acyclic coloring was introduced by Grünbaum [5] and is a generalization of point arboricity.A proper k-coloring of the vertices of a graph Gis said to be acyclic if G contains no two-colored cycle. The acyclic chromatic number of a graph G, denoted by a(G), is the minimum value of k for which G has an acyclic k-coloring. Let a(n) denote the maximum value of the acyclic chromatic number among all graphs of genus n. In [5], Grünbaum conjectured that a(0) = 5 and proved that a(0)≤9. The conjecture was proved by Borodin [3] after the upper bound was improved three times in [7], [1] and [6]. In [2], we proved that a(1)≤a(0) + 3. The purpose of this paper is to prove the followingTheorem. Any graph of genus n>0 can be acyclically colored with 4n + 4 colors.It is not known for any n>0 whether a(n)>H(n), the Heawood number [8]. 
Albertson, Michael O.; Berman, David M. An acyclic analogue to Heawood's theorem. Glasgow mathematical journal, Tome 19 (1978) no. 2, pp. 163-166. doi: 10.1017/S001708950000358X
@article{10_1017_S001708950000358X,
     author = {Albertson, Michael O. and Berman, David M.},
     title = {An acyclic analogue to {Heawood's} theorem},
     journal = {Glasgow mathematical journal},
     pages = {163--166},
     year = {1978},
     volume = {19},
     number = {2},
     doi = {10.1017/S001708950000358X},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/S001708950000358X/}
}
TY  - JOUR
AU  - Albertson, Michael O.
AU  - Berman, David M.
TI  - An acyclic analogue to Heawood's theorem
JO  - Glasgow mathematical journal
PY  - 1978
SP  - 163
EP  - 166
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1017/S001708950000358X/
DO  - 10.1017/S001708950000358X
ID  - 10_1017_S001708950000358X
ER  - 
%0 Journal Article
%A Albertson, Michael O.
%A Berman, David M.
%T An acyclic analogue to Heawood's theorem
%J Glasgow mathematical journal
%D 1978
%P 163-166
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1017/S001708950000358X/
%R 10.1017/S001708950000358X
%F 10_1017_S001708950000358X

[1] 1.Albertson, M. O. and Berman, D. M., Every planar graph has an acyclic 7-coloring, Israel J. Math., 28 (1977), 169–174. Google Scholar | DOI

[2] 2.Albertson, M. O. and Berman, D. M., The acyclic chromatic number, Proc. 1th S-E Conf. Combinatorics, Graph Theory, and Computing (Utilitas Math., 1976), 51–60. Google Scholar

[3] 3.Borodin, O. V., A proof of B. Grünbaum's conjecture on the acyclic 5-colorability of planar graphs (Russian), Dokl. Akad. Nauk SSSR 231 (1976), 18–20. Google Scholar

[4] 4.Brooks, R. L., On coloring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197. Google Scholar | DOI

[5] 5.Griinbaum, B., Acyclic colorings of planar graphs, Israel J. Math. 14 (1973), 390–408. Google Scholar

[6] 6.Kostochka, A. V., Acyclic 6-coloring of planar graphs (Russian), Diskret. Analiz. 28 (1976), 40. Google Scholar

[7] 7.Mitchem, J., Every planar graph has an acyclic 8-coloring, Duke Math. J. 41 (1974), 177–181. Google Scholar | DOI

[8] 8.Ringel, G., Map Color Theorem (Springer, 1974). Google Scholar | DOI

Cité par Sources :