### Abstract

Let G be an edge-colored graph. The minimum color degree of G is the minimum number of different colors appearing on the edges incident with the vertices of G. In this paper, we study the existence of properly edge-colored cycles in (not necessarily properly) edge-colored complete graphs. Fujita and Magnant (2011) conjectured that in an edge-colored complete graph on n vertices with minimum color degree at least (n+1)∕2, each vertex is contained in a properly edge-colored cycle of length k, for all k with 3≤k≤n. They confirmed the conjecture for k=3 and k=4, and they showed that each vertex is contained in a properly edge-colored cycle of length at least 5 when n≥13, but even the existence of properly edge-colored Hamilton cycles is unknown (in complete graphs that satisfy the conditions of the conjecture). We prove a cycle extension result that implies that each vertex is contained in a properly edge-colored cycle of length at least the minimum color degree.

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

Pages (from-to) | 1235-1241 |

Journal | Discrete mathematics |

Volume | 340 |

Issue number | 6 |

DOIs | |

Publication status | Published - Jun 2017 |

### Keywords

- Edge-colored graph
- Complete graph
- Properly colored cycle

## Cite this

Li, R., Broersma, H. J., Xu, C., & Zhang, S. (2017). Cycle extension in edge-colored complete graphs.

*Discrete mathematics*,*340*(6), 1235-1241. https://doi.org/10.1016/j.disc.2017.01.023