Hostname: page-component-7b7567c8c-slfcl Total loading time: 0 Render date: 2026-11-19T12:04:36.446Z Has data issue: false hasContentIssue false

An extremal function for contractions of graphs

Published online by Cambridge University Press:  24 October 2008

Andrew Thomason
Affiliation:
St John's College, Cambridge, England CB2 1TP†
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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)).

Information

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1984