Anti-Ramsey Coloring For Matchings

The anti-Ramsey number AR(Kn, G) is defined to be the maximum number of colors in an edge coloring of Kn which does not contain any rainbow copy of G. It was introduced by Erdos et al. in 1970s. They proved that the anti-Ramsey number was related to the Turan number. Later, the researchers studied the anti-Ramsey number in some special graphs Like cycles, paths, matchings. Furthermore, the anti-Ramsey number of the complete bipartite graphs had been considered and made some good results. But the extremal coloring for the anti-Ramsey number in graphs (called anti-Ramsey coloring) are still no progress.In this master thesis, we study the anti-Ramsey coloring in complete bipartite graph and complete graph. The thesis consists of three chapters.The first chapter is devoted to the introducing the research backgrounds and pre-requisite knowledge for the anti-Ramsey numbers in graphs. We give a chief survey of anti-Ramsey number and state the main results obtained. In the second chapter, we study the anti-Ramsey coloring for matchings in complete bipartite graphs. We show the uniqueness of the extremal edge-coloring, which is called the anti-Ramsey coloring, for the rainbow matchings in Km,n-The characterizations of the anti-Ramsey coloring for matching in complete bipartite graphs are determined. In the last chapter, we s-tudy the anti-Ramsey coloring for matchings in complete graphs. Also, we show that the uniqueness and determine the characterizations of the anti-Ramsey coloring for the matchings in complete graphs.