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.
|Number of pages||7|
|Journal||Graphs and Combinatorics|
|State||Published - Dec 1987|
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics