An improved bound for the monochromatic cycle partition number (Q859613)

Let \(p(r)\) denote the least number of monochromatic cycles (including degenerate ones such as single vertices and edges) required to partition \(V(K_n)\) for all \(n\) when \(E(K_n)\) has been \(r\)-colored (\(r\geq2\)). That \(p(r)\) is well-defined follows from the existence of a constant \(c\) such that \(p(r)\leq cr^2\log r\), proved by \textit{P. Erdős, A. Gárfás} and \textit{L. Pyber} [J. Comb. Theory, Ser. B 51, 90--95 (1991; Zbl 0766.05062)]. The main result is a significant sharpening of the above inequality: for each \(r\geq2\) there exists a constant \(n_0\) such that for any \(n\geq n_0\) and any \(r\)-coloring of \(E(K_n)\), the set \(V(K_n)\) can be partitioned into \(\leq100r\log r\) vertex-disjoint monochromatic cycles.