Lower bound of the Hadwiger number of graphs by their average degree (Q760439): Difference between revisions

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.