On graphs with subgraphs having large independence numbers

Noga Alon, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)149-157
Number of pages9
JournalJournal of Graph Theory
Volume56
Issue number2
DOIs
StatePublished - Oct 2007
Externally publishedYes

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