On graphs with subgraphs of large independence numbers

Details On graphs with subgraphs of large independence numbers On graphs with subgraphs of large independence numbers

2007-06-27

arxiv.org/abs/0706.4099v1

Mathematics

Combinatorics

Scientific paper

Let G be a graph on n vertices in which every induced subgraph on s=\log^3 n vertices has an independent set of size at least t=\log n. What is the largest q=q(n) so that every such G must contain an independent set of size at least q ? This is one of several related questions raised by Erdos and Hajnal. We show that q(n)=\Theta(\log^2 n/\log \log n), investigate the more general problem obtained by changing the parameters s and t, and discuss the connection to a related Ramsey-type problem.

Affiliated with

Also associated with

No associations

Rating

On graphs with subgraphs of large independence numbers 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 On graphs with subgraphs of large independence numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On graphs with subgraphs of large independence numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455868