Mathematical Proceedings of the Cambridge Philosophical Society

Research Article

An extremal function for contractions of graphs

Andrew Thomasona1

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.