### Abstract

Let G be a graph on n vertices in which every induced subgraph on s = log^{3}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 the several related questions raised by Erdos and Hajnal. We show that q(n) = O&Theta(log^{2}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.

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

## Fingerprint Dive into the research topics of 'On graphs with subgraphs having large independence numbers'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Sudakov, B. (2007). On graphs with subgraphs having large independence numbers.

*Journal of Graph Theory*,*56*(2), 149-157. https://doi.org/10.1002/jgt.20264