Achromatic numbers of random graphs
Colin McDiarmid · Mathematical Proceedings of the Cambridge Philosophical Society · 1982
Abstract The achromatic number ψ(G) of a graph G is the greatest number of colours in a proper colouring of the vertices of G such that for every pair of colours some vertex of the first colour and some vertex of the second colour are adjacent. We prove that almost all graphs Gn with n vertices satisfy n/(k+l) < ψ(Gn) < n/(k–1), where k = k(n) = (log2n)½. We show also that the achromatic number is a ‘global’ invariant.