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  ≥    α    2    k  +  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.
['Shinya Fujita', 'Henry Liu', 'Amites Sarkar']
Highly Connected Subgraphs of Graphs with Given Independence Number (Extended Abstract)