Monochromatic Cycle Partitions in Local Edge Colorings. Issue 2 (14th April 2015)

• Record Type: Journal Article
• Authors: Conlon, David; Stein, Maya
• Is Part Of: Journal of graph theory. Volume 81:Issue 2(2016)
• Page Start: 134
• Page End: 145
• Publication Date: 2015-04-14
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21867
• Languages: English
• ISSNs: 0364-9024

Abstract

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.