Large nearly regular induced subgraphs

Details Large nearly regular induced subgraphs Large nearly regular induced subgraphs

2007-10-10

arxiv.org/abs/0710.2106v2

Mathematics

Combinatorics

Scientific paper

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+\epsilon with epsilon>0 sufficiently small, f(n,c) \geq n^{\Omega(\epsilon^2/ \ln (1/\epsilon))}. (iii) \Omega (\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.

Affiliated with

Also associated with

No associations

Rating

Large nearly regular induced subgraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large nearly regular induced subgraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large nearly regular induced subgraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-541039