zbMATH — the first resource for mathematics

A generalized Ramsey problem. (English) Zbl 0969.05042
Let \(f(n)\) be the minimum number such that there is a proper edge-coloring of \(K_n\), the complete graph on \(n\) vertices using \(f(n)\) colors with no path or cycle of 4 edges using one or two colors. Let \(f(n,p,q)\) denote the minimal number of colors needed to color the edges of \(K_n\) such that \(p\)-clique uses at least \(q\) colors on its edges. The author develops the relationship between \(f(n)\) and \(f(n,5,9)\) and exploits that relationship to prove:
Theorem 1.
(i) \({1+ \sqrt 5\over 2} n-3\leq f(n)\leq 2n^{1+ c/\sqrt{\log n}}\),
(ii) \({1+\sqrt 5\over 2} n-3\leq f(n,5,9)\leq 2n^{1+ c/\sqrt{\log n}}\), where \(c\) is a positive constant.

05C55 Generalized Ramsey theory
Full Text: DOI