Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 2016 | Submitted
Journal Article Open

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.

Attached Files

Submitted - 1403.5975.pdf


Files (175.8 kB)
Name Size Download all
175.8 kB Preview Download

Additional details

August 20, 2023
October 18, 2023