Premium
Induced subgraphs of prescribed size
Author(s) -
Alon Noga,
Krivelevich Michael,
Sudakov Benny
Publication year - 2003
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.10117
Subject(s) - combinatorics , mathematics , induced subgraph , graph , omega , induced subgraph isomorphism problem , factor critical graph , clique , discrete mathematics , graph power , line graph , vertex (graph theory) , voltage graph , physics , quantum mechanics
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 Erdős 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^{\Omega} (\sqrt { \log\, n})$ . © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 239–251, 2003