An extremal function for contractions of graphs
- 1 March 1984
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Proceedings of the Cambridge Philosophical Society
- Vol. 95 (2) , 261-265
- https://doi.org/10.1017/s0305004100061521
Abstract
The function c(p) is defined for positive integers p ≥ 4 bywhere > denotes contraction. Random graph examples showIn 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)).Keywords
This publication has 3 references indexed in Scilit:
- Extremal Graph TheoryPublished by Taylor & Francis ,2013
- Hadwiger's Conjecture is True for Almost Every GraphEuropean Journal of Combinatorics, 1980
- Homomorphies tze f r GraphenMathematische Annalen, 1968