Color degree and monochromatic degree conditions for short properly colored cycles in edge-colored graphs

Shinya Fujita, Ruonan Li, Shenggui Zhang* (Corresponding Author)

*Corresponding author for this work

    Research output: Contribution to journalArticleAcademicpeer-review

    8 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    For an edge-colored graph, its minimum color degree is defined as the minimum number of colors appearing on the edges incident to a vertex and its maximum monochromatic degree is defined as the maximum number of edges incident to a vertex with a same color. A cycle is called properly colored if every two of its adjacent edges have distinct colors. In this article, we first give a minimum color degree condition for the existence of properly colored cycles, then obtain the minimum color degree condition for an edge-colored complete graph to contain properly colored triangles. Afterwards, we characterize the structure of an edge-colored complete bipartite graph without containing properly colored cycles of length 4 and give the minimum color degree and maximum monochromatic degree conditions for an edge-colored complete bipartite graph to contain properly colored cycles of length 4, and those passing through a given vertex or edge, respectively.

    Original languageEnglish
    Pages (from-to)362-373
    Number of pages12
    JournalJournal of graph theory
    Volume87
    Issue number3
    DOIs
    Publication statusPublished - 1 Mar 2018

    Keywords

    • UT-Hybrid-D
    • 05C38
    • complete (bipartite) graphs
    • edge-colored graphs
    • maximum monochromatic degree
    • minimum color degree
    • properly colored cycles
    • 05C15

    Fingerprint Dive into the research topics of 'Color degree and monochromatic degree conditions for short properly colored cycles in edge-colored graphs'. Together they form a unique fingerprint.

    Cite this