Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T13:14:21.650Z Has data issue: false hasContentIssue false

An acyclic analogue to Heawood's theorem

Published online by Cambridge University Press:  18 May 2009

Michael O. Albertson
Affiliation:
Department Of Mathematics, Smith College, Northampton, Mass. 01063
David M. Berman
Affiliation:
Department of Mathematics, University of New Orleans, New Orleans, La. 70122
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 following

Theorem. 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].

Information

Type
Research Article
Copyright
Copyright © Glasgow Mathematical Journal Trust 1978