Large nearly regular induced subgraphs
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
For a real c \geq 1 and an integer n, let f(n,c) denote the maximum integer f so 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 $(n,1) was posed long time ago by Erdos, Fajtlowicz and Staton. In this note we obtain the following upper and lower bounds for the asymptotic behavior of f(n,c):
(i) For fixed c>2.1, n^{1-O(1/c)} \leq f(n,c) \leq O(cn/\log n).
(ii) For fixed c=1+εwith epsilon>0 sufficiently small, f(n,c) \geq n^{Ω(ε^2/ \ln (1/ε))}.
(iii) Ω(\ln n) \leq f(n,1) \leq O(n^{1/2} \ln^{3/4} n).
An analogous problem for not necessarily induced subgraphs is briefly considered as well.