An improved bound for the monochromatic cycle partition number (Q859613): Difference between revisions

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.