Jun 21, 2016: Ruonan Li: Cycle extension in edge-colored complete graphs

June 21, 2016Cycle extension in edge-colored complete graphs
Room: HB 2BRuonan Li
12:30-13:30

We study the existence of properly edge-colored cycles in edge-colored complete graphs. In 2011, Fujita and Magnant 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. 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, i.e., the smallest number of different colors appearing on the edges incident with the vertices of the graph.