A generalized Ramsey problem
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: \hskip 10mm Theorem 1. \hskip 10mm (i) \({1+ \sqrt 5\over 2} n-3\leq f(n)\leq 2n^{1+ c/\sqrt{\log n}}\), \hskip 10mm (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.
scientific article; zbMATH DE number 1506832