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.