zbMATH — the first resource for mathematics

An extremal function for contractions of graphs. (English) Zbl 0551.05047
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

05C35 Extremal problems in graph theory
60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.