Research On Edge-colored Complete Graphs Under Restrictions Of Color-degree Sum And Color Number

Let(G,c)be a nontrivial simple edge-colored graph.A path or a cycle of(G,c)is called properly colored if every two consecutive edges of it have different colors.For each vertex v of(G,c),the color degree of v.denoted by d_G^c(v),is the number of different colors on the edges incident to v;the maximum monochrofmatic degree of vmdenoted by ?min(v),is the maximum number of the same color on the edges incident to v.The minimum color degree of(G,c),denoted by ?^c(G),is the minimum value of d_G^c(v)over all vertices v G V(G);and the maximum monochromatic degree of(G,c),denoted by Amon(G),is the maximum value of?^mon(v)over all vertices v G V(G).In this thesis,we study the properly colored paths and properly colored cycles in the edge-colored graphs under the restriction conditions of "the sum of edges and colors”,"color-degree sum of the graphs" and "color number of the K₄-subgraphs",respectively.The main results are as follows:(1)Let(G,c)be an edge-colored graph on n vertices.If the sum of edges and colors or the color-degree sum of(G,c)is at least n(n+1)/2+k,then(G.c)has at least k properly colored cycles of length 4.(2)Let(G,c)be an edge-colored complete graph on n(n? 4)vertices.If every K₄-subgraph of(G,c)has at least three colors,then(G,c)has a properly colored Hamiltonian path.Meanwhile,if it further holds that either ?^c'(G)?n+1/2 or ?^mon(G)<[n/2]?then(G,c)has a properly colored cycle of length at least n-1.Moreover,if the length of the longest properly colored cycle C=v₁v₂…v_lv₁ of(G,c)is n-1,then there exist two adjacent vertices v_i,v_i+1 in C such that wv_iv_i+1w forms a monochromatic triangle in(G,c),where w is the unique vertex in V(G)\V(C).