An extremal function for contractions of graphs 论文
1984Mathematical Proceedings of the Cambridge Philosophical Society引用 330
Mathematical Approximation and IntegrationComplexity and Algorithms in GraphsMarkov Chains and Monte Carlo Methods
摘要
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) [log 2 ( 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.68 p √(log 2 p )(l + ο(l)).