Abstract
An edgecolored 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 edgecolored 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 edgecolored 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 edgecolored graphs. In Chapter 3, we characterize the structure of an edgecolored 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 edgecolored 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 edgecolored 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 edgecolored graphs and directed graphs, and find that the class of PC theta graphs plays an important role in characterizing the difference between edgecolored 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.
The first three chapters of this thesis study short or long PC cycles in edgecolored 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 edgecolored graphs. In Chapter 3, we characterize the structure of an edgecolored 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 edgecolored 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 edgecolored 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 edgecolored graphs and directed graphs, and find that the class of PC theta graphs plays an important role in characterizing the difference between edgecolored 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 language  English 

Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  2 Feb 2018 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036544719 
DOIs  
Publication status  Published  18 Jan 2018 
Fingerprint Dive into the research topics of 'Properly colored cycles in edgecolored graphs'. Together they form a unique fingerprint.
Cite this
Li, R. (2018). Properly colored cycles in edgecolored graphs. Enschede: University of Twente. https://doi.org/10.3990/1.9789036544719