Induced subgraphs of prescribed size

Noga Alon, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let q(G) denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open problem of Erdos and McKay we show that every graph G on n vertices for which q(G) ≤ C log n contains an induced subgraph with exactly y edges, for every y between 0 and nδ(C). Our methods enable us also to show that under much weaker assumption, i.e., q(G) ≤ n/14, G still must contain an induced subgraph with exactly y edges, for every y between 0 and eΩ(√log n).

Original languageEnglish (US)
Pages (from-to)239-251
Number of pages13
JournalJournal of Graph Theory
Volume43
Issue number4
DOIs
StatePublished - Aug 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Cliques and independent sets
  • Induced subgraphs
  • Ramsey graphs

Fingerprint Dive into the research topics of 'Induced subgraphs of prescribed size'. Together they form a unique fingerprint.

  • Cite this