Edge-coloring cliques with three colors on all 4-cliques
For integers \(n,p\) and \(q\), a \((p,q)\)-coloring of \(K_n\) is a coloring of the edges of \(K_n\) in which the edges of every \(p\)-cligue together receive at least \(q\) colors. Let \(f(n,p,q)\) denote the minimum number of colors in a \((p,q)\)-coloring of \(K_n\). The author proves that \(f(n,4,3)<\exp(\sqrt{c\log n}(1+O(1)))\), where \(c=4\log 2\). This improves the corresponding result by \textit{P. Erdős} and \textit{A. Gyárfás} [A variant of the classical Ramsey problem, Combinatorica 17, No. 4, 459-467 (1997; Zbl 0910.05034)].
scientific article; zbMATH DE number 1261230