Article contents
Achromatic numbers of random graphs
Published online by Cambridge University Press: 24 October 2008
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.
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 92 , Issue 1 , July 1982 , pp. 21 - 28
- Copyright
- Copyright © Cambridge Philosophical Society 1982
References
REFERENCES
- 9
- Cited by