On graphs with subgraphs of large independence numbers

2007/06/27 by Alon, Noga, Sudakov, Benny
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0706.4099

Abstract

Let G be a graph on n vertices in which every induced subgraph on s=log³ n vertices has an independent set of size at least t=log n. What is the largest q=q(n) so that every such G must contain an independent set of size at least q ? This is one of several related questions raised by Erdos and Hajnal. We show that q(n)=Θ(log² n/log log n), investigate the more general problem obtained by changing the parameters s and t, and discuss the connection to a related Ramsey-type problem.

Related

• Large independent sets from local considerations
• Independent sets in graphs with given minimum degree
• Large cliques and independent sets all over the place
• Counting independent sets in triangle-free graphs
• Maximum independent sets near the upper bound