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 . Combining their result with some probabilistic arguments, we prove the following Ramsey type theorem conjectured by Erdös  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)|
|Number of pages||8|
|Journal||Random Structures and Algorithms|
|State||Published - Jan 1 1996|
All Science Journal Classification (ASJC) codes
- Computer Graphics and Computer-Aided Design
- Applied Mathematics