zbMATH — the first resource for mathematics

Acyclic coloring of graphs. (English) Zbl 0735.05036
A proper vertex colouring (adjacent vertices have distinct colours) of a finite simple undirected graph \(G\) is acyclic if there is no cycle in \(G\) induced by the vertices of any two of the colours. The acyclic chromatic number \(A(G)\) of \(G\) is the least number of colours in an acyclic colouring of \(G\). The main result \[ A(G)=O(d^{4/3}) \hbox{ as } d\to \infty \] for every graph \(G\) of maximum degree \(d\) settles a problem of Erdős. All proofs rely heavily on probabilistic arguments.
Reviewer: U.Baumann

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Albertson, The acyclic chromatic number, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing pp 51– (1976) · Zbl 0344.05116
[2] Alon, The linear arboricity of graphs, Isr. J. Math. 62 pp 311– (1988) · Zbl 0673.05019
[3] Alon, Star arboricity
[4] Bollobás, Random Graphs (1985)
[5] Bollobás, Extremal Graph Theory (1978)
[6] Borodin, On acyclic colourings of planar graphs, Discrete Math. 25 pp 211– (1979)
[7] Erdōs, Infinite and Finite Sets (1975)
[8] Grunbaum, Acyclic colorings of planar graphs, Isr. J. Math. 14 pp 390– (1973)
[9] Montgomery, Topics in Multiplicative Number Theory, Lecture Notes in Maths pp 227– (1971) · Zbl 0216.03501
[10] Spencer, Ten Lectures on the Probabilistic Method (1987)
[11] Toft, Pitman Research Notes in Mathematics Series 218, in: Graph Colorings pp 9– (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.