Abstract
Let G be a graph on n vertices in which every induced subgraph on s = log3n 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 the several related questions raised by Erdos and Hajnal. We show that q(n) = O&Theta(log2n/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.
Original language | English (US) |
---|---|
Pages (from-to) | 149-157 |
Number of pages | 9 |
Journal | Journal of Graph Theory |
Volume | 56 |
Issue number | 2 |
DOIs | |
State | Published - Oct 2007 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
Keywords
- Independence numbers
- Ramsey-type problems