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.