Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-29T20:32:57.557Z Has data issue: false hasContentIssue false
  • English
  • Français

An extremal function for contractions of graphs

Published online by Cambridge University Press:  24 October 2008

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

Abstract

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

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 95 , Issue 2 , March 1984 , pp. 261 - 265
Copyright
Copyright © Cambridge Philosophical Society 1984

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bollobás, B.. Extremal Graph Theory (Academic Press, 1978).Google Scholar
[2]Bollobás, B., Catlin, P. and Erdös, P.. Hadwiger's conjecture is true for almost every graph. European J. Combin. 1 (1980), 195–199.CrossRefGoogle Scholar
[3]Kostochka, A. V.. A lower bound for the Hadwiger number of a graph as a function of the average degree of its vertices. Discret. Analyz. Novosibirsk 38 (1982), 37–58.Google Scholar
[4]Mader, W.. Homomorphiesätze für Graphen. Math. Ann. 178 (1968), 154–168.CrossRefGoogle Scholar