Extremal Problems In Edge-Coloured Graphs

In this paper,we mainly study the problems related t.o subgraphs of edge-colored graphs.Given a graph G=(V,E)and an edge-coloring ? of G such that?:E?{1,2,...,k}.We say a subgraph H of G is properly colored,if for any two adjacent edges e,e' of G we have ?(e)??(e').H is rainbow if for any two distinct edges e,e' of H we have ?(e)??(e').H is strongly edge-colored,if any path of H with length at most 3 is rainbow.A subgraph M of G is a matching,if any two edges of M are vertex-disjoint.We first proved that if a strongly edge-colored graph G satisfies |G|?2?(G)+1,then G contains a rainbow matching of size ?(G).This theorem partly confirmed a conjecture of Wang,Yan and Yu.We also proved that if a strongly edge-colored graph G satisfies ?(G)?2|G|/3,then G contains a rainbow hamiltonian cycle,which can be seen as the Dirac's theorem of strongly edge-colored form.We further proposed a related conjecture.For general edge-colored graph,let color degree dc(v)be the number of colors used by edges incident to v,and ?c(G)is the minimum color degree among all the vertices in G.We studied the properly colored spanning tree,and proved that if G satisfies ?c(G)?2|G|/2,then G contains a properly colored spanning tree,and the lower bound is tight.Ron Aharoni recently conjectured that if G1,...,Gn are monochromatic graphs defined on the same vertex set V of size n where any two graphs Gi and Gj are colored with distinct colors for 1?i<j?n.If ?(Gi)?(1/2+?)n for 1?i?n,then there exists a rainbow hamiltonian cycle.We used the absorption technique developed by Rodl,Rucinski,and Szemeredi,giving an asymptotic solution to this conjecture and generalize it to a pancyclic form.Actually,we proved that for any ?>0,there exists an N0 such that when n>N0,if monochromatic graphs G1,...,Gn are defined on the same vertex set of size n.where the colors of Gi and Gj are distinct for 1?i?j?n,which satisfies ?(Gi)?(1/2+?)n for 1?i?n.then we can find rainbow cycles of size l(3?l?n).