Independence number and clique minors
Ken‐ichi Kawarabayashi, Zi‐Xia Song · Journal of Graph Theory · 2007
Abstract The Hadwiger number ${h}({G})$ of a graph G is the maximum integer t such that ${K}_{t}$ is a minor of G. Since $\chi({G})\cdot\alpha({G})\geq |{G}|$ , Hadwiger's conjecture implies that ${h}({G})\cdot \alpha({G})\geq |{G}|$ , where $\alpha({G})$ and $|{G}|$ denote the independence number and the number of vertices of G, respectively. Motivated by this fact, it is shown that $(2\alpha({G})-{2})\cdot {h}({G})\geq |{G}|$ for every graph G with $\alpha({G})\geq {3}$ . This improves a theorem of Duchet and Meyniel and a recent improvement due to Kawarabayashi et al. © Wiley Periodicals, Inc. J. Graph Theory 56: 219–226, 2007