Large nearly regular induced subgraphs

Noga Alon, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

For a real c ≥ 1 and an integer n, let f(n, c) denote the maximum integer f such that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum degree is at most c times the minimum degree. Thus, in particular, every graph on n vertices contains a regular induced subgraph on at least f(n, 1) vertices. The problem of estimating f(n, 1) was posed long ago by Erdös, Fajtlowicz, and Staton. In this paper we obtain the following upper and lower bounds for the asymptotic behavior of f(n, c): (i) For fixed c > 2.1, n1-0(1/c) ≤ f(n, c) ≤ O(cn/ logra). (ii) For fixed c = 1 + η with η > 0 sufficiently small, f(n,c) ≥ nΩ(η2 /ln(1/η)). (iii) Ω(lnra) ≤ f(n, 1) ≤ O(n1/2 ln3/4ra). An analogous problem for not necessarily induced subgraphs is briefly considered as well.

Original languageEnglish (US)
Pages (from-to)1325-1337
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Volume22
Issue number4
DOIs
StatePublished - 2008

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Induced subgraphs
  • Ramsey-type problem
  • Regular subgraphs

Fingerprint Dive into the research topics of 'Large nearly regular induced subgraphs'. Together they form a unique fingerprint.

Cite this