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 - Oct 1996 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics