An improved bound for the monochromatic cycle partition number (Q859613)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An improved bound for the monochromatic cycle partition number |
scientific article |
Statements
An improved bound for the monochromatic cycle partition number (English)
0 references
16 January 2007
0 references
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.
0 references
complete graph
0 references
edge-coloring
0 references
monochromatic partition
0 references
regularity lemma
0 references