Properly Colored Cycles In Edge-Colored Graphs

The existence of subgraphs with certain color patterns in edge-colored graphs has attracted much attention of scholars in the field of graph theory.Particularly,the existence of properly colored cycles is widely concerned.Not only because of the important role that properly colored cycles play in the research of properly colored subgraphs,but also for the applications in other research fields,such as molecular biology,social science etc.This thesis studies the existence of properly colored cycles and related problems.The main results are as following.1.By defining the concept of“acyclic closure”in edge-colored graphs,a more transparent proof of the structural theorem on edge-colored graphs containing no properly colored cycles has been obtained.2.The existence of short properly colored cycles,especially,cycles of lengths3 or 4 in edge-colored graphs has been studied.We obtain a color degree sum condition of each pair of adjacent vertices for the existence of properly colored triangles and characterize the structure of extremal graphs.We also obtain a characterization of edge-colored complete bipartite graphs containing no prop-erly colored cycle of length 4.Under this characterization,we get a minimum color degree condition and a maximum monochromatic degree condition for the corresponding existence problem.Moreover,we give some sufficient conditions to guarantee that each vertex(edge)of edge-colored complete bipartite graphs is contained in a properly colored cycle of length 4.3.Focusing on a conjecture proposed by Fujita and Magnant on the existence of properly colored Hamilton cycles in edge-colored complete graphs,we study the existence of long properly colored cycles.By proving a cycle extension theorem in edge-colored complete graphs,we show that each edge-colored K_nwith minimum color degree at least(n+1)/2 must contain a properly colored cycle of length at least the minimum color degree.We also study the existence of large properly colored Theta graphs and obtain that each edge-colored K_nwith minimum color degree at least(n+1)/2 either contains a properly colored Hamilton cycle or each maximal properly colored cycle could be transformed into a properly colored Theta graph by adding a chord.4.The existence of vertex-disjoint properly colored cycles are concerned in edge-colored complete graphs.We conjecture that each edge-colored K_nwith maximum monochromatic degree at most n-3k+1 contains k vertex-disjoint properly colored cycles.The case that k≤2 is confirmed.For k≥3,we characterize the structure of possible minimum counterexamples.5.We consider the partition problem in edge-colored graphs and conjecture that the vertex-set of each edge-colored graph G with minimum color degree at least a+b+1(a,b∈N)can be partitioned into A and B such that G[A]and G[B]are of color degree at least a and b,respectively.The case that a,b≤2 is confirmed.6.We study the relationship between properly colored cycles and directed cycles.We propose the concept“multipartite tournament”and show that Theta graphs play a very important role in characterizing the difference between edge-colored complete graphs and multipartite tournaments.According to a certain transformation method,we illustrate that directed graphs can be regarded as a special class of edge-colored graphs.Particularly,we explain how the vertex-disjoint cycles problem and the partition problem in edge-colored graphs relate to those corresponding problems in directed graphs.