Highly Connected Subgraphs of Graphs with Given Independence Number (Extended Abstract)

Let G be a graph on n vertices with independence number α. What is the largest k-connected subgraph that G must contain? We prove that if n is sufficiently large (n≥α2k+1 will do), then G contains a k-connected subgraph on at least n/α vertices. This is sharp, since G might be the disjoint union of α equally-sized cliques. For k≥3 and α=2,3, we shall prove that the same result holds for n≥4(k−1) and n≥27(k−1)4 sharp.