Properly edge-coloured subgraphs in colourings of bounded degree
The smallest \(n\) such that every coloring of the edges of the \(n\)-vertex complete graph \(K_n\) must contain a monochromatic star \(K_{1,s+1}\) or a properly edge-colored \(K_t\) is denoted by \(f(s,t)\), Its existence is guaranteed by the Erdős-Rado Canonical Ramsey theorem. The authors prove that {\parindent=7mm \begin{itemize}\item[(i)]\(f(s,3)=5s/2+1\) if \(s\) is even and \(f(s,3)=5s/2-1/2\) if \(s\) is odd, \item[(ii)]\((f(2,4)=10\), \item[(iii)]\(f(s,4)\leq 15s/2\), and \item[(iv)]\(f(s,t)\leq 3^52^{-7}(s-1)(t-1)^2+3\). \end{itemize}} The upper bounds for \(f(s,4)\) and \(f(s,t)\) in (iii) and (iv) improve the known upper bounds obtained in [\textit{N. Alon, T. Jiang, Z. Miller} and \textit{D. Pritkin}, ``Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints'', Random Struct. Algorithms 23, No. 4, 409--433 (2003; Zbl 1037.05033)]
scientific article; zbMATH DE number 5999823