An extremal function for contractions of graphs
An extremal function for contractions of graphs
复制标题
图收缩的极值函数
DOI：
10.1017/s0305004100061521
复制
发表时间：
1984
影响因子：
0.8
通讯作者：
A. Thomason
中科院分区：
文献类型：
--
作者：
A. Thomason
摘要通过>表示收缩的函数C（P）定义为正整数P≥4。最近，Kostochka表明P√（log P）是C（P）的正确顺序。
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)).