### Abstract

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

*Discrete mathematics*,

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

}

*Discrete mathematics*, vol. 340, no. 6, pp. 1235-1241. https://doi.org/10.1016/j.disc.2017.01.023

**Cycle extension in edge-colored complete graphs.** / Li, Ruonan; Broersma, Haitze J.; Xu, Chuandong; Zhang, Shenggui.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Cycle extension in edge-colored complete graphs

AU - Li, Ruonan

AU - Broersma, Haitze J.

AU - Xu, Chuandong

AU - Zhang, Shenggui

PY - 2017/6

Y1 - 2017/6

N2 - 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.

AB - 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.

KW - Edge-colored graph

KW - Complete graph

KW - Properly colored cycle

U2 - 10.1016/j.disc.2017.01.023

DO - 10.1016/j.disc.2017.01.023

M3 - Article

VL - 340

SP - 1235

EP - 1241

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 6

ER -