Research On Anti-Ramsey Numbers

A subgraph H of an edge-colored graph G is rainbow if all of its edges have different colors.The anti-Ramsey number Ar?G,H?is defined as the maximum number k that there is no rainbow copy of H in k edge-coloring.The anti-Ramsey number was first studied by Erd?s et al.in 1973.In this thesis,we give a new method to study the anti-Ramsey number.Let G be a graph and?be a set of subgraphs of G.We use Ar_G???to denote the maximum number of colors in an edge-coloring of G with no rainbow copy in?.We construct a graph L?G,??whose vertex set V(L?G,??={G₁,G₂,....,G_s}and edge set E?L?G,???={f₁,f₂...f_m},where G_i??and G_i,G_j?f_kif and only if G_iand G_jhave a common edge in G.If every edge of graph G is related to at most two subgraphs of G in?,then we proved that Ar_G???=|E?G?|-|?|+M,where M is the independent cycle number of L?G,??.As the application of the theorem,we obtained some results about the anti-Ramsey number.