Monochromatic partitions in local edge colorings (Q2220970): Difference between revisions

An edge coloring of a graph is called a local \(r\)-coloring if the edges incident to any vertex are colored with at most \(r\) distinct colors. The two main results established in this paper are as follows.\par (1) Let \(r \geq 1\) and \(n \geq r^{2(r+2)}\) be integers. Let the edges of the complete graph \(K_n\) on \(n\) vertices be colored with a local \(r\)-coloring. Then, there are at most \(r\) monochromatic trees of radius 2 such that each of them is of a distinct color and the vertex sets of them partition the vertex set of \(K_n\). \par (2) For a given integer \(r \geq 2\) there is a constant \(n_0 = n_0(r)\) such that if the edges of the complete graph \(K_n\), \(n \geq n_0\), are colored with a local \(r\)-coloring, then its vertex set can be partitioned into at most \(200r \log r\) monochromatic cycles.