Research On Properly Colored Cycles In Edge-colored Complete Graphs And Complete Bipartite Graphs

For an edge-colored graph Gc,the maximum monochromatic degree of Gc,denoted by ?mon(Gc),is the maximum number of edges of the same color incident with a vertex of Gc.When we consider a vertex subset X(?)V(G),the corresponding maximum value for the vertices of X is denoted by ?mom(X).A subgraph of Gc is properly colored if every two adjacent edges in this subgraph have distinct colors.A subgraph of Gc is monochromatic if all the edges in this subgraph have the same color.Gc is properly vertex-m-pancyclic if every vertex of Gc is on a cycle of length k for each k=m,m+1,…,|V(G)|.Gc is properly even vertex-pancyclic if every vertex of G is on a cycle of length k for each even number k with 4?k?|V(G)|.In this thesis,we study the properly colored cycles in edge-colored complete graphs and complete bipartite graphs under some conditions of the maximum monochromatic degree.The main results are as follows.(1)Let Gc be an edge-colored complete graph on n? 4 vertices such that?mon(Gc)<[n/2].If Gc contains no monochromatic triangles,then G is properly vertex-4-pancyclic.Moreover,we characterize the coloring structure of every edgecolored complete graph which satisfies the above conditions and has no rainbow triangles.The first result partially solves a conjecture proposed by Bollobás and Erdos which says that:if Gc is an edge colored complete graph and ?mon(Gc)<[n/2].then Gc contains a properly colored Hamilton cycle.(2)Let Gc be an edge-colored complete bipartite graph with bipartition[A,B].where |A|=m and |B|=n.Suppose that ?mon(A)<n/2,?mom(B)<m/2,and Gc has no monochromatic 3-paths.If for each proper cycle C of Gc with A\V(C)?(?) and B\V(C)?(?) we have |TA(C)|=|TB(C)|?1,then Gc is properly even vertex-pancyclic.Here,for each X ??A,B?,TX(C)is the set consisting of all the vertices of X\V(C)each of which does not follow the colors of C at all.