Mathematical Proceedings of the Cambridge Philosophical Society · 1984 · 324 citations · 1 references
Mathematical ProgrammingGraph MinorGeometric Graph TheoryEngineeringGraph TheoryRandom GraphExtremal Graph TheoryLower BoundNetwork AnalysisCorrect OrderEducationExtremal FunctionExtremal CombinatoricsDiscrete MathematicsMetric Graph TheoryCombinatorial OptimizationFunction C
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)).
1