Clique minors in graphs and their complements

A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t greater than or equal to 1 be an integer, and let G be a graph on 12 vertices with no minor isomorphic to k(t+1). Kostoch ka conjectures that there exists a constant c =c(t) independent of G such t hat the complement of G has a minor isomorphic to K-s, where s = [1/2(1 + 1 /t) n - c]. We prove that Kostochka's conjec- -ture is equivalent to the co njecture of Duchet and Meyniel that every graph with no minor isomorphic to Kt+1, has an independent set of size at least n/t. We deduce that Kostochk a's conjecture holds for all integers t less than or equal to 5, and that a weaker for with s replaced by s' = [1/2( 1 + 1/(2t)) n - c] holds For all integers t greater than or equal to 1. (C) 2000 Academic Press.