Study Of Anti-Ramsey Number For Matchings

An edge-colored graph is called a rainbow graph if the colors on its edges are distinct. The anti-Ramsey number AR(G, H) is defined to be the maximum num-ber of colors in an edge coloring of G which does not contain any rainbow copy of H. The anti-Ramsey number was introduced by Erdos et al. in 1970s, which is one of the rainbow generalizations of the classical Ramsey problem. It has been shown that the anti-Ramsey number AR(Kn,H) is not related to the Ramsey number but closely related to Turan number. During the last years, especially the recent decades, researchers made deep study of the anti-Ramsey number in some special graph classes. The anti-Ramsey numbers of several graph classes have been determined, including cycles, paths, complete graph, matchings in complete graphs and complete bipartite graphs. In the early study, the researchers always considered the complete graphs or complete bipartite graphs as host graph. Since the recent years, some researchers began to consider the general graphs as host graphs.In this master thesis, we study the anti-Ramsey number for matchings in graphs (mainly bipartite graph), and the anti-Ramsey number problem of matchings in some special edge-colored graph. The thesis consists of four chapters.In Chapter 1, we introduce some basic definitions and notations. Also, we give a chief survey of anti-Ramsey number and state the main results obtained.In Chapter 2, we study the anti-Ramsey number for matchings in regular bipartite graphs. We give the anti-Ramsey number for matchings in regular bipartite graphs under some conditions, which improves the results of Li & Xu. Also, we give the bounds of anti-Ramsey number for matchings in k(k≥ 4)-regular bipartite graphs.In Chapter 3, we study the anti-Ramsey number for matchings in the (cartesian) product graph Pr × Pn. We get the formula of anti-Ramsey number for matchings in Pr×Pn.In Chapter 4, we study the anti-Ramsey number for matchings in a kind of special edge-colored (i.e., Gallai-colored) complete graphs. First we give the minimum edge number of rainbow matchings in the k-allai edge-colored graphs. Based on it, we give the anti-Ramsey number for matchings in Gallai-colored complete graphs.