Monochromatic Cycle Partitions in Local Edge Colorings
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.
Additional Information© 2015 Wiley. Issue online 08 December 2015; version of record online 14 April 2015; manuscript revised 28 January 2015; manuscript received 24 March 2014. The first author is supported by a Royal Society University Research Fellowship and the second author is supported by the Fondecyt grants 11090141 and 1140766.
Submitted - 1403.5975.pdf