A generalized Ramsey problem. (English) Zbl 0969.05042

Axenovich, Maria

Discrete Math. 222, No. 1-3, 247-249 (2000).

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.

Reviewer: Jack E.Graver (Syracuse)

MSC:

05C55

Generalized Ramsey theory

Keywords:

generalized Ramsey problem; edge-coloring