Monochromatic Cycle Partitions in Local Edge Colorings

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.

Files

Additional details