Properly colored cycles in edge-colored graphs
Ruonan is a double degree PhD-student in the Research Group Formal Methods and Tools at the University of Twente. Her supervisor is Hajo Broersma from the Faculty of Electrical Engineering, Mathematics and Computer Science and Shenggui Zhang from the Nortwestern Polytechnical University in People's republic of China.
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 directed 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.
