### Abstract

Let G = (V,E) be a graph on n vertices with average degree t ≥ 1 in which for every vertex v E V the induced subgraph on the set of all neighbors of v is r-colorable. We show that the independence number of G is at least c/log(r + 1) n/t log t, for some absolute pos.tive constant c. This strengthens a well-known result of Ajtai, Komlós, and Szemerédi [1]. Combining their result with some probabilistic arguments, we prove the following Ramsey type theorem conjectured by Erdös [4] in 1979. There exists an absolute constant c' > 0 so that in every graph on n vertices in which any set of ⌊ √n ⌋ vertices contains at least one edge, there is some set of ⌊√n ⌋ vertices that contains at least c'√n log n edges.

Original language | English (US) |
---|---|

Pages (from-to) | 271-278 |

Number of pages | 8 |

Journal | Random Structures and Algorithms |

Volume | 9 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1996 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics