Problem Statement
Let $f(d)$ be the maximal acyclic chromatic number of any graph with maximum degree $d$ - that is, the vertices of any graph with maximum degree $d$ can be coloured with $f(d)$ colours such that there is no edge between vertices of the same colour and no cycle containing only two colours.
Estimate $f(d)$. In particular is it true that $f(d)=o(d^2)$?
Estimate $f(d)$. In particular is it true that $f(d)=o(d^2)$?
Categories:
Graph Theory Chromatic Number
Progress
It is easy to see that $f(d)\leq d^2+1$ using a greedy colouring. Erdős had shown $f(d)\geq d^{4/3-o(1)}$.Resolved by Alon, McDiarmid, and Reed [AMR91] who showed\[\frac{d^{4/3}}{(\log d)^{1/3}}\ll f(d) \ll d^{4/3}.\]
Source: erdosproblems.com/797 | Last verified: January 16, 2026