Premium
On graphs with subgraphs having large independence numbers
Author(s) -
Alon Noga,
Sudakov Benny
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20264
Subject(s) - combinatorics , mathematics , independence number , graph , independent set , induced subgraph , binary logarithm , discrete mathematics , vertex (graph theory)
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 Erdős and Hajnal. We show that ${q}{(n)}= \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. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 149–157, 2007