On the minimum of the Hadwiger number for graphs with given mean degree of vertices. (Russian) Zbl 0544.05037

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ń


05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs


Zbl 0165.574