Abstract
A coloring of the edges of a graph is called a local k-coloring if every vertex is incident to edges of at most k distinct colors. For a given graph G, the local Ramsey number, rlock(G), is the smallest integer n such that any local k-coloring of Kn, (the complete graph on n vertices), contains a monochromatic copy of G. The following conjecture of Gyárfás et al. is proved here: for each positive integer k there exists a constant c = c(k) such that rlock(G) ≤ crk(G), for every connected grraph G (where rk(G) is the usual Ramsey number for k colors). Possible generalizations for hypergraphs are considered.
Original language | English |
---|---|
Pages (from-to) | 67-73 |
Number of pages | 7 |
Journal | Graphs and Combinatorics |
Volume | 3 |
Issue number | 1 |
DOIs | |
State | Published - Dec 1987 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics