# 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.

##### MSC:
 05C55 Generalized Ramsey theory
##### Keywords:
generalized Ramsey problem; edge-coloring
Full Text: