An extremal function for contractions of graphs
Author:
- 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
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)).Keywords
This publication has 2 references indexed in Scilit:
- Hadwiger's Conjecture is True for Almost Every GraphEuropean Journal of Combinatorics, 1980
- Homomorphies tze f r GraphenMathematische Annalen, 1968