×

zbMATH — the first resource for mathematics

The extremal function for complete minors. (English) Zbl 1024.05083
Summary: Let \(c(t)\) be the minimum number \(c\) such that every graph \(G\) with \(e(G)\geq c|G|\) contracts to a complete graph \(K_t\). We show that \(c(t)= (\alpha+ o(1))t\sqrt{\log t}\), where \(\alpha= 0.319\dots\) is an explicit constant. Random graphs are extremal graphs.

MSC:
05C83 Graph minors
05C35 Extremal problems in graph theory
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N.; Spencer, J., The probabilistic method, (1992), Wiley New York
[2] Bollobás, B., Extremal graph theory, (1978), Academic Press London · Zbl 0419.05031
[3] Bollobás, B., Random graphs, (1985), Academic Press London/New York · Zbl 0567.05042
[4] Bollobás, B.; Catlin, P.; Erdős, P., Hadwiger’s conjecture is true for almost every graph, Europ. J. combin. theory, 1, 195-199, (1980) · Zbl 0457.05041
[5] Bollobás, B.; Reed, B.; Thomason, A., An extremal function for the achromatic number, Contemp. math., 147, 161-165, (1993) · Zbl 0787.05053
[6] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. math. statist., 23, 493-509, (1952) · Zbl 0048.11804
[7] Chung, F.R.K.; Graham, R.L.; Wilson, R.M., Quasi-random graphs, Combinatorica, 9, 345-362, (1989) · Zbl 0715.05057
[8] Fernandez de la Vega, W., On the maximum density of graphs which have no subcontraction to K^s, Discrete math., 46, 109-110, (1983) · Zbl 0517.05045
[9] Dirac, G.A., Homomorphism theorems for graphs, Math. ann., 153, 69-80, (1964) · Zbl 0115.41005
[10] Duchet, P.; Kaneti, V., Sur la contractabilité d’un graphe orienté en K*4, Discrete math., 130, 57-68, (1994) · Zbl 0817.05029
[11] Z. Füredi, unpublished.
[12] Hadwiger, H., Über eine klassifikation der streckenkomplexe, Vierteljahresschr. naturforsch. ges. Zürich, 88, 133-142, (1943) · Zbl 0061.41308
[13] Jacob, H.; Meyniel, H., Extensions of Turán’s and Brooks’s theorems and new motions of stability and colouring in digraphs, Ann. discrete math., 17, 365-370, (1983) · Zbl 0525.05027
[14] Jagger, C., An extremal function for digraph subcontraction, J. graph theory, 21, 343-350, (1996) · Zbl 0844.05046
[15] Jagger, C., Tournaments as strong subcontractions, Discrete math., 176, 177-184, (1997) · Zbl 0894.05030
[16] Jørgensen, L., Contractions to K8, J. graph theory, 18, 431-448, (1994) · Zbl 0808.05064
[17] Karabeg, A.; Karabeg, D., Graph compaction, (), 44-51
[18] Kostochka, A.V., The minimum hadwiger number for graphs with a given Mean degree of vertices, Metody diskret. analiz., 38, 37-58, (1982) · Zbl 0544.05037
[19] Kostochka, A.V., A lower bound for the hadwiger number of graphs by their average degree, Combinatorica, 4, 307-316, (1984) · Zbl 0555.05030
[20] Mader, W., Homomorphieeigenschaften und mittlere kantendichte von graphen, Math. ann., 174, 265-268, (1967) · Zbl 0171.22405
[21] Mader, W., Homomorphiesätze für graphen, Math. ann., 178, 154-168, (1968) · Zbl 0165.57401
[22] W. Mader, personal communication.
[23] Thomason, A., An extremal function for contractions of graphs, Math. proc. Cambridge philos. soc., 95, 261-265, (1984) · Zbl 0551.05047
[24] Thomason, A., Pseudo-random graphs, (), 307-331
[25] Thomason, A., Complete minors in pseudo-random graphs, Random structures and algorithms, 17, 26-28, (2000) · Zbl 0955.05092
[26] Wagner, K., Beweis einer abschwächung der hadwiger-vermutung, Math. ann., 153, 139-141, (1964) · Zbl 0192.30002
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.