Cycle extension in edge-colored complete graphs

Ruonan Li, Haitze J. Broersma, Chuandong Xu, Shenggui Zhang

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)

    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 languageEnglish
    Pages (from-to)1235-1241
    JournalDiscrete mathematics
    Volume340
    Issue number6
    DOIs
    Publication statusPublished - Jun 2017

    Keywords

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

    Cite this