zbMATH — the first resource for mathematics

Lower bound of the Hadwiger number of graphs by their average degree. (English) Zbl 0555.05030
A contraction of a connected graph \(G=(V,E)\) to the complete graph with r vertices is considered as a surjection \(\psi: V\to \{1,2,...,r\}\) with the properties that every subgraph of G induced by \(\psi^{-1}(i)\) is connected and for any integers i, j from \(\{\) 1,2,...,r\(\}\), \(i\neq j\), there exist vertices \(v\in \psi^{-1}(i)\) and \(w\in \psi^{-1}(j)\) such that \((v,w)\in E.\) the greatest r such that G can be contracted onto the complete graph with r vertices is called the Hadwiger number \(\eta\) (G) of G. The minimum of \(\eta\) (G) for graphs \(G=(V,E)\) with \(| E| /| V| \geq k\) is denoted by \(\eta\) (k). Further for each positive integer k the function \(w(k)=\min \{\eta (G): \chi (G)\geq k\}.\) The well- known conjecture of Hadwiger says that \(w(k)=k\) for any k.
In the present paper it is proved that \(\eta (k)\geq k/270\sqrt{\log k}\) and \(w(k)\geq k/540\sqrt{\log k}\) for \(k\geq 2\). From this corollary follows that if k is large enough, then Hadwiger’s conjecture is true for almost all graphs with n vertices and kn edges.
Reviewer: B.Zelinka

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
60C05 Combinatorial probability
Full Text: DOI
[1] P. Erdos, J. Spencer,Probabilistic methods in combinatorics, Academic Press, New York-London, 1974. · Zbl 0308.05001
[2] H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Viert.Naturforsch. Ges. Zürich,88 (1943), 133–142. · Zbl 0061.41308
[3] A. D. Korshunov, On the chromatic number of graphs onn vertices (in Russian),Metody diskretnogo analiza v teorii bulevyh funkcij i skhem,35 (1980), 15–45.
[4] A. V. Kostochka, On the minimum Hadwiger number of graphs with given average degree (in Russian),submitted to Diskretnij Analiz. · Zbl 0595.05041
[5] W. Mader, Homomorphiesätze für Graphen,Math. Annalen,178 (1968), 154–168. · Zbl 0165.57401 · doi:10.1007/BF01350657
[6] Z. Miller, Contractions of graphs: A theorem of Ore and an extremal problem,Discrete Math.,21 (1978), 261–273. · Zbl 0378.05043 · doi:10.1016/0012-365X(78)90158-9
[7] K. Wagner, Beweis einer Abschwächung der Hadwiger–Vermutung,Math. Annalen,153 (1964), 139–141. · Zbl 0192.30002 · doi:10.1007/BF01361181
[8] B. Zelinka, On some graph-theoretical problems of V. G. Vizing,Cas. Pestov. Math.,98 (1973), 56–66. · Zbl 0256.05116
[9] A. A. Zykov, On the edge number of graphs with no greater Hadwiger number than 4,Prikladnaja matematika i programmirovanije,7 (1972), 52–55.
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.