Properly colored cycles in edge-colored graphs

Ruonan Li

Research output: ThesisPhD Thesis - Research UT, graduation UT

Abstract

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.
LanguageEnglish
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Broersma, Haitze J., Supervisor
  • Zhang, S., Supervisor
Thesis sponsors
Award date2 Feb 2018
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-4471-9
DOIs
StatePublished - 18 Jan 2018

Fingerprint

Edge-colored Graph
Cycle
Degree Condition
Directed Graph
Complete Bipartite Graph
Graph in graph theory
Complete Graph
Multipartite Tournaments
Degree Sum
Molecular Biology

Cite this

Li, R. (2018). Properly colored cycles in edge-colored graphs Enschede: University of Twente DOI: 10.3990/1.9789036544719
Li, Ruonan . / Properly colored cycles in edge-colored graphs. Enschede : University of Twente, 2018. 153 p.
@phdthesis{05f13878fad040579aefef7b18a7d3eb,
title = "Properly colored cycles in edge-colored graphs",
abstract = "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.",
author = "Ruonan Li",
note = "IDS Ph.D. Thesis Series No. 18-457",
year = "2018",
month = "1",
day = "18",
doi = "10.3990/1.9789036544719",
language = "English",
isbn = "978-90-365-4471-9",
publisher = "University of Twente",
address = "Netherlands",
school = "University of Twente",

}

Li, R 2018, 'Properly colored cycles in edge-colored graphs', University of Twente, Enschede. DOI: 10.3990/1.9789036544719

Properly colored cycles in edge-colored graphs. / Li, Ruonan .

Enschede : University of Twente, 2018. 153 p.

Research output: ThesisPhD Thesis - Research UT, graduation UT

TY - THES

T1 - Properly colored cycles in edge-colored graphs

AU - Li,Ruonan

N1 - IDS Ph.D. Thesis Series No. 18-457

PY - 2018/1/18

Y1 - 2018/1/18

N2 - 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.

AB - 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.

U2 - 10.3990/1.9789036544719

DO - 10.3990/1.9789036544719

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-4471-9

PB - University of Twente

CY - Enschede

ER -

Li R. Properly colored cycles in edge-colored graphs. Enschede: University of Twente, 2018. 153 p. Available from, DOI: 10.3990/1.9789036544719