Article
Highly connected subgraphs of graphs with given independence number
European Journal of Combinatorics
(2018)
Abstract
Let G be a graph on n vertices with independence number α. We prove that if n is sufficiently large (n≥α²k+1 will do), then G always contains a k-connected subgraph on at least n ∕ α vertices. The value of n ∕ α 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 results hold for n≥4(k-1) and n≥27(k-1)/4 respectively, and that these lower bounds on n are sharp.
Disciplines
Publication Date
May 1, 2018
DOI
10.1016/j.ejc.2018.01.004
Citation Information
Shinya Fujita, Henry Liu and Amites Sarkar. "Highly connected subgraphs of graphs with given independence number" European Journal of Combinatorics Vol. 70 (2018) p. 212 - 231 Available at: http://works.bepress.com/amites_sarkar/23/