Kostochka, A. V. On the minimum of the Hadwiger number for graphs with given mean degree of vertices. (Russian) Zbl 0544.05037 Metody Diskretn. Anal. 38, 37-58 (1982). Hadwiger number \(\eta\) (G) of a graph G is the minimum order of a complete graph onto which G can be contracted. The author improves a result of W. Mader [Math. Ann. 178, 154-168 (1968, Zbl 0165.574)] by showing that minimum Hadwiger number among graphs with average degree of vertices not smaller than 2k is \(O(k/\sqrt{1n\quad k})\) as \(k\to \infty\). Corollary 3 is to be read as follows. For large enough k, Hadwiger’s conjecture is true for almost all graphs of order n and size kn. Reviewer: Z.Skupień Cited in 4 ReviewsCited in 86 Documents MSC: 05C35 Extremal problems in graph theory 05C15 Coloring of graphs and hypergraphs Keywords:Hadwiger conjecture; pseudocolouring; contractions Citations:Zbl 0165.574 PDFBibTeX XMLCite \textit{A. V. Kostochka}, Metody Diskretn. Anal. 38, 37--58 (1982; Zbl 0544.05037)