Properly colored subgraphs in edge-colored graphs

Properly colored cycles are closely related to directed cycles in directed graphs, and play an important role in molecular biology, transportation and communication, social sciences and other fields. In this thesis, we study the existence of properly colored cycles in edge-colored graphs and related cyclic properties, like the existence of properly colored cycles, cycle-factors and properly colored cycles of different or all lengths. The main results are as following.

We study the existence of short properly colored cycles in edge-colored complete graphs and edge-colored bipartite graphs. We give a sufficient condition for the existence of properly colored 4-cycles and characterize the extremal graphs. We also characterize the extremal graphs for several known results on the existence of properly colored triangles. Then we give sufficient conditions guaranteeing that every vertex is contained in a properly colored triangle and 4-cycle, respectively. Moreover, we obtain a sufficient condition for the existence of properly colored cycles of length at most 6 in edge-colored bipartite graphs.

By characterizing edge-colored complete graphs containing no PC odd cycles, we give an efficient algorithm for deciding the existence of PC odd cycles in an edge-colored complete graph. Moreover, we give an equivalent characterization of the existence of properly colored cycles of length k modulo m in edge-colored complete graphs.

We obtain sufficient conditions for the existence of k (vertex-disjoint) properly colored cycles of different lengths in edge-colored complete graphs.

We obtain a sufficient condition for the existence of properly colored cycle-factors in edge-colored bipartite graphs. Our result is a generalization of Lo's result on properly colored cycle-factors in edge-colored graphs in [SIAM J. Discrete Math. 28 (2014) 18--36].

We obtain a necessary and sufficient condition for edge-colored complete bipartite graphs containing no monochromatic paths of length three to be PC even vertex-pancyclic. Our result is a generalization of a result of Häggkvist and Manoussakis on bipartite tournaments in [Combinatorica 9 (1989) 33–38].