Study For Rainbow Matchings

Rainbow matchings is a hot topics in graph theory during the last decades.The famous Ryser conjecture(i.e.,each Latin square of odd order contains a Latin transver-sal)is equivalent to that every proper n-edge-coloring of Kn,n for odd n contains a rainbow perfect matching.The existence conditions of the rainbow matching in the edge colored graph have been extensively studied.On the other hand,rainbow number of matchings is from the perspective of extreme graph theory to study the existence of rainbow matchings.The rainbow number of graphs equal to the anti-Ramsey number of graphs plus one,where the anti-Ramsey number of graphs is proposed by Erdos et al.in the 1970s which is closely related to Turan number of graphs.In this paper,we study the existence of rainbow matchings in edge colored graphs.We mainly consider the largest order of and results rainbow matchings in some special edge colored graphs and rainbow number of matching in some planar graphs.The main structure of this thesis are divided into the following four parts.In the first chapter,we mainly introduces the basic concepts and terms of graph theory involved in this thesis.The research background and research status of rainbow matchings in edge colored graphs are described in detail.Also,we briefly describe the main results of this thesis.In the second chapter,we study the existence conditions of rainbow matchings in the edge-coloring graphs.We mainly consider the problem of the maximum rainbow matching in a weakened strong edge colored graph(ie,the semi-strong edge coloring of the graph).The relationship between the order of the maximal rainbow matching and the order of the graph is depicted.In the third chapter,we study the problem of matching rainbow number in the maximal outerplanar graph.We first give the upper and lower bounds of the rainbow number for matching of size k.We use the same technique to improve the upper bound of the rainbow number for matching of the size k in a subfamily of the plane trian-gulation graphs.And we give the exact value of the rainbow numbers of some small matchings in the maximal outerplanar graph.In the fourth chapter,we study the matching rainbow numbers in the Halin graph.We first give the upper and lower bounds of the rainbow number for matching of size k and give the exact values of the rainbow numbers of some small matchings.