×

On sub-Ramsey numbers. (English) Zbl 0603.05031

Given a graph G and a natural number k, the sub-Ramsey number sr(G,k) is the least integer m so that, if the complete graph on m vertices is edge colored in such a way that no color is used more than k times, then there is an isomorphic copy of G all of whose edges have distinct colors.
The paper includes several proofs of the existence of sr(G,k) as well as some exact values and bounds for sr(G,k), in the case G is a complete graph. For example: Theorem: Let \(n\geq 4\) and \(k\geq 2\). Then, \[ k(n- 1)+1\leq sr(K_ n,k)\leq \{n(n-1)(n-2)(k-1)+3\}/4. \]
Reviewer: J.E.Graver

MSC:

05C55 Generalized Ramsey theory
PDFBibTeX XMLCite