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

Abstract

The function c(p) is defined for positive integers p ≥ 4 by

S0305004100061521_eqnU1

where > denotes contraction. Random graph examples show

S0305004100061521_eqnU2

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)

Correspondence:

p1 Present address: Department of Mathematics, Louisiana State University, Boton Rouge, LA 70803, U.S.A.