## Abstract

Let G be an edge-colored graph. The minimum color degree δ^{c}(G) of G is the largest integer k such that for every vertex ν, there are at least k distinct colors on edges incident to ν. We say that G is properly colored if no two adjacent edges have the same color. In this paper, we show that every edge-colored graph G with δ^{c}(G) ≥ 2|G|/3 contains a properly colored 2-factor. Furthermore, we show that for any ε > 0 there exists an integer n_{0} such that every edge-colored graph G with |G| = n ≥ n_{0} and δ^{c}(G) ≥ (2/3 + ε)n contains a properly colored cycle of length ℓ for every 3 ≤ ℓ ≤ n. This result is best possible in the sense that the statement is false for δ^{c}(G) < 2n/3.

Original language | English |
---|---|

Pages (from-to) | 18-36 |

Number of pages | 19 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 28 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2 Jan 2014 |

## Keywords

- 2-factor
- Hamiltonian cycle
- Proper edge-coloring

## ASJC Scopus subject areas

- General Mathematics