An extremal function for contractions of graphs. (English) Zbl 0551.05047

Thomason, Andrew

Math. Proc. Camb. Philos. Soc. 95, 261-265 (1984).

For finite graphs \(G\) and \(H\) the author writes \(G>H\) when \(H\) may be obtained from \(G\) by a sequence of deletions and contractions of edges. For integers \(p\geq 4\), \(c(p)\) is defined to be \(\inf \{e(G)/v(G): G>K_ p\}\). “Since a random graph of order \(n\) with edges chosen with probability \(1-q\) almost certainly does not contract to a \(K_ p\) where \(p=n\{\log (1/q)/\log (n)\}^{\frac{1}{2}}\{1+o(1)\}\) [B. Bollobás, P. Catlin, and P. Erdős, Eur. J. Comb. 1, 195–199 (1980; Zbl 0457.05041)] …we see, on taking \(q=0.284\), that \(c(p)\geq 0.265p \log_ 2p\) for large \(p\).” W. Mader [Math. Ann. 178, 154–168 (1968; Zbl 0165.57401)] has shown that \(c(p)\leq 8(p-2)\log_ 2(p-2)\). The author improves an upper bound of A. V. Kostochka [Metody Diskretn. Anal. 38, 37–58 (1982; Zbl 0544.05037)] (that \(c(p)<324\sqrt{\log_ 2p})\) by proving that \(c(p)\leq 2.68p\sqrt{\log_ 2p}\) for large \(p\).

Reviewer: W. G. Brown

MSC:

05C35	Extremal problems in graph theory
60C05	Combinatorial probability
05C80	Random graphs (graph-theoretic aspects)

Keywords:

contractions of edges; Hadwiger number; average degree

References:

[1]	DOI: 10.1007/BF01350657 · Zbl 0165.57401 · doi:10.1007/BF01350657
[2]	Bollob?s, Extremal Graph Theory (1978)
[3]	Bollob?s, European J. Combin. 1 pp 195– (1980) · Zbl 0457.05041 · doi:10.1016/S0195-6698(80)80001-1
[4]	Kostochka, Discret. Analyz. Novosibirsk 38 pp 37– (1982)