The Rainbow Matching Problem Of The Bipartite Graphs

The rainbow problem is one of the important research contents in graph theory. Back in the fifties and sixties of last century at home and abroad have a lot of great study, but due to the application significance when the rainbow problem not particularly prominent, rainbow also has not been widely pay attention to it. Recently with the development of science and technology, the rise of computer science, graph theory has also been more and more attention, and at the same time the rainbow problem has become a hot issue by more people. Now people are very wide range of content of the rainbow problem, according to the way of dyeing can be divided into the normal dyeing of the rainbow and non-normal dyeing of the rainbow. According to the specific content of the study of the rainbow, there are many Rainbow Road, rainbow circle, rainbow tree, rainbow circle, single color tree, single color matching, rainbow matching, and so on. These are all put forward in the basis of dyeing has great application value.If the graph is the vastness of the universe, then rainbow is the entire solar system, rainbow problem involves the problem of not only the amount is numberless as the sand, now there are many kinds and different, to the careful introduction of the system, workload is really too huge, in order not to waste everyone too much force, I in this thesis mainly introduces the and my research content about some background knowledge. In Chapter one the research back-ground 1.2.1 mainly introduces and Latin transversal about some background knowledge in order to facilitate the people to be more receptive to this. In the first chapter, the paper introduces the basic concepts, the research process and the classical research methods of edge coloring and rainbow matching of graphs in 1.2.2. Knowledge of the notoriously rainbow is now no longer a problem in graph theory, related to the computer network, combinatorics, number and so on, so in the research process of this paper also uses the knowledge of these.Bipartite graph in the rainbow matching the originator of the problem is the ancient people for Latin transversal conjecture and research, later trans- formed into a rainbow matching of. Latin transversal is transformed from the practical problems in real life of that graph to describe Latin transversal can be such that a Latin transversal of is Latin square A in n a different different columns of distinct elements from a collection of, the Latin square is by n column and n elements of matrix An×n. Many years ago, Aharoni and Berger proposed such a conjecture:any one of the n from the same one or two figure of the size of the n+1 match of the set family, contains a size of n perfect rainbow match. Although this conjecture has not yet been resolved, but the future generations to do a lot of approximation of the results of this conjecture and conjecture. In the first chapter, the research process and the results of Aharoni and Berger conjecture in the background of 1.2.3 are introduced in detail.When d> 1 and F1,..., Fk edge with the Ministry of twelve hiris. When meet the △(Fi)< d and |Fi|> (k-1)d, the family of sets F1,...,Fk exists a size matching for k perfect rainbow. This is later Aharoni and Howard and proposed conjecture. We know that this conjecture is not true, because when n= 1, this conjecture is wrong. The second chapter mainly prove the family of sets F1,..., Fk with G(A∪B, E) in the edge set, when the meet △(Fi)< 2and |Fi|= n, including i= 1,..., k, n=[23/7k], the family of sets F={F1,..., Fk} has a size k perfect rainbow matching. Although the process of proof of this conclusion is more complex, but it is clear that the idea is quite clear. Proof of this topic is divided two, draws a lot of previous proof methods, especially the predecessors of bipartite graph matching the rainbow family set matching problem of proof techniques, such as edge replacement, reduction to absurdity, the pigeonhole principle proof method.The third chapter of this paper mainly studies from the angle of rainbow road, the main content of the research is about the rainbow road of the com-plete graph. We know that for a normal staining in any complete graph Kn, there a size (3/4-o(1))n rainbow road. The third chapter mainly prove the a normal staining of the complete bipartite graph Kn,n biggest Rainbow Road, the length of a lower bound is 2/3n, and make this a conjecture. In the course of the proof is based on previous experience,using the method of contradiction, the pigeonhole principle and method.The fourth chapter is the second chapter some simple inferences,i.e. if the family of sets F1,...,Fk belong ti G(A∪B,E)in the edge set,when the meet△(Fi)≤2 and |Fi|=n,design Fi is an odd number of laps and odd way and the quantity for mi,i=1,…,k,m=min{m1,………,mk}. If m+n≥[23/7k],set group F={F1,..,Fk}exists a size matching for k perfect rainbow.If F1,...,Fkwith a graph G(A∪B,E)in the edge set,when the meet△(Fi))≤2 and |Fi|=2k-1.When k=1,2,3,5,7,9 set family F={F1,…,Fk)exists a size for k perfect rainbow matching.Inspired by our rainbow matching problem can also be considered from the perspective of the circle.The fifth chapter introduces the practical application value of the research content in this paper,which can make us have a clear understanding of the rainbow matching problem.