Connected matchings and Hadwiger's conjecture
Zoltán Füredi, András Gyárfás, Gábor Simonyi · Combinatorics Probability Computing · 2005
Hadwiger's well known conjecture (see the survey of Toft [9]) states that any graph $G$ has a $K_{\chi(G)}$ minor, where $\chi(G)$ is the chromatic number of $G$ . Let $\alpha(G)$ denote the independence (or stability) number of $G$ , namely the maximum number of pairwise nonadjacent vertices in $G$ . It was observed in [1], [4], [10] that via the inequality $\chi(G)\ge {|V(G)|\over \alpha(G)}$ , Hadwiger's conjecture implies Conjecture 1.1. Any graph G on n vertices contains a $K_{\lceil {n\over \alpha(G)}\rceil}$ as a minor .