a1 St John's College, Cambridge, England CB2 1TP†
The function c(p) is defined for positive integers p ≥ 4 by
where > denotes contraction. Random graph examples show
In 1968 Mader showed that c(p) ≤ 8(p − 2) [log2 (p − 2)] and more recently Kostochka showed that p√(log p) is the correct order for c(p). We present a simple argument showing c(p) ≤ 2.68p √(log2p)(l + ο(l)).
(Received July 25 1983)
(Revised November 01 1983)
p1 Present address: Department of Mathematics, Louisiana State University, Boton Rouge, LA 70803, U.S.A.