Premium
Monochromatic Cycle Partitions in Local Edge Colorings
Author(s) -
Conlon David,
Stein Maya
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21867
Subject(s) - monochromatic color , combinatorics , mathematics , colored , vertex (graph theory) , disjoint sets , complete graph , edge coloring , fractional coloring , graph , discrete mathematics , graph coloring , graph power , line graph , physics , optics , materials science , composite material
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.