Monochromatic Cycle Partitions in Local Edge Colorings. Issue 2 (14th April 2015) - Conlon, David; Stein, Maya
Abstract: An edge coloring of a graph is said to be an r ‐local coloring if the edges incident to any vertex are colored with at most r colors. Generalizing a result of Bessy and Thomassé, we prove that the vertex set of any 2‐locally colored complete graph may be partitioned into two disjoint monochromatic cycles of different colors. Moreover, for any natural number r, we show that the vertex set of any r ‐locally colored complete graph may be partitioned into O ( r 2 log r ) disjoint monochromatic cycles. This generalizes a result of Erdős, Gyárfás, and Pyber.