Linear upper bounds for local Ramsey numbers (Q1087887): Difference between revisions

Let G be a graph. By a ''local k-coloring'' of G we mean an edge coloring of G, in which, at most k distinct colors occur on the edges incident to any vertex of G. For the graph G, the local Ramsey number \(r^ k_{loc}(G)\) is the minimum integer n so that, in every local k-coloring of the edges of the complete graph on n vertices, there exists a monochromatic subgraph isomorphic to G. Clearly \(r^ k(G)\leq r^ k_{loc}(G)\) where \(r^ k(G)\) is the usual Ramsey number. The main result of this paper is: Theorem 1. For every positive integer k, there exists a constant \(c=c(k)\) such that \(r^ k_{loc}(G)\leq cr^ k(G)\), for every connected graph G.