Properly colored cycles in edge-colored graphs

Ruonan Li

    Research output: ThesisPhD Thesis - Research UT, graduation UT

    260 Downloads (Pure)


    An edge-colored graph is a graph with each edge assigned a color. A properly colored cycle ( or PC cycle for short ) is a cycle such that consecutive edges are assigned distinct colors. Properly colored cycles have attracted much attention during the past decades, not only because of many interesting conjectures and results on this specifics topic, but also for the fact that studying PC cycles in edge-colored graphs generalizes the study of cycles in directed graphs. PC cycles have also appeared in applications, e.g. in social science and molecular biology. In this thesis, we are interested in theoretical aspects only.

    The first three chapters of this thesis study short or long PC cycles in edge-colored graphs, complete graphs and complete bipartite graphs. In Chapter 2, a color degree sum condition for pairs of adjacent vertices are given for the existence of PC triangles in edge-colored graphs. In Chapter 3, we characterize the structure of an edge-colored complete bipartite graphs without containing a PC cycle of length 4. Based on this characterization, we give a minimum color degree condition and a maximum monochromatic degree condition for an edge-colored complete bipartite graph to contain a PC cycle of length 4, and for PC cycles of length 4 passing through a given vertex or edge, respectively. In Chapter 4, a PC cycle extension result is obtained, which relates to a Conjecture given by Fujita and Magnant.

    Works in the last three chapters are motivated by and dedicated to the close relationship between PC cycles in edge-colored graphs and directed cycles in directed graphs. In particular, the results in Chapters 5 and 6 are related to a conjecture on disjoint cycles in directed graphs due to Bermond and Thomassen. In Chapter 7, we aim to study the difference between edge-colored graphs and directed graphs, and find that the class of PC theta graphs plays an important role in characterizing the difference between edge-colored complete graphs and multipartite tournaments. We also give color number condition and minimum color degree condition for the existence of small and large PC theta graphs, respectively.

    Throughout this thesis, we have investigated the existence of many types of PC cycles and other PC subgraphs ( e.g. PC theta graphs) related to PC cycles under different conditions. Despite our new contributions, many problems and conjectures remain unresolved. We also leave several new open questions and posed a number of new conjectures to stimulate further research. We hope that this will attract the attention of many researchers and spur the developments in this exciting area.
    Original languageEnglish
    QualificationDoctor of Philosophy
    Awarding Institution
    • University of Twente
    • Broersma, Hajo, Supervisor
    • Zhang, S., Supervisor, External person
    Thesis sponsors
    Award date2 Feb 2018
    Place of PublicationEnschede
    Print ISBNs978-90-365-4471-9
    Publication statusPublished - 18 Jan 2018


    Dive into the research topics of 'Properly colored cycles in edge-colored graphs'. Together they form a unique fingerprint.

    Cite this