### 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 language | English (US) |
---|---|

Pages (from-to) | 239-251 |

Number of pages | 13 |

Journal | Journal of Graph Theory |

Volume | 43 |

Issue number | 4 |

DOIs | |

State | Published - Aug 2003 |

Externally published | Yes |

### 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

Alon, N., Krivelevich, M., & Sudakov, B. (2003). Induced subgraphs of prescribed size.

*Journal of Graph Theory*,*43*(4), 239-251. https://doi.org/10.1002/jgt.10117