Monochromatic Cycle Partitions in Local Edge Colorings |
| |
Authors: | David Conlon Maya Stein |
| |
Institution: | 1. MATHEMATICAL INSTITUTE, UNIVERSITY OF OXFORD, ANDREW WILES BUILDING, RADCLIFFE OBSERVATORY QUARTER, OXFORD, UNITED KINGDOM;2. CENTRO DE MODELAMIENTO MATEMáTICO, UNIVERSIDAD DE CHILE, SANTIAGO, CENTRO RM, CHILE |
| |
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 disjoint monochromatic cycles. This generalizes a result of Erd?s, Gyárfás, and Pyber. |
| |
Keywords: | |
|
|