On the complexity of approximating the Hadwiger number
Unless P = NP there is no polynomial time approximation scheme (PTAS) for the problem of finding, for a graph G, the largest h such that the complete graph K-h is a minor of G. (C) 2008 Elsevier B.V. All rights reserved.
