Existence of rainbow matchings in properly edge-colored graphs

Abstract

Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let δ denote the minimum degree of G. We show that if |V(G)| > (δ² + 14δ + 1)/4, then G has a rainbow matching of size δ, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18: #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition (X, Y) and max{|X|, |Y|} > (δ² + 4δ − 4)/4, then G has a rainbow matching of size δ.

Keywords

Rainbow matching / properly edge-colored graph

References

[1] Bondy J. A., Murty U. S. R. Graph Theory with Applications, 1976, New York: Macmillan Press

[2] Brualdi R. A., Ryser H. J. Combinatorial Matrix Theory, 1991, Cambridge: Cambridge University Press

[3] Kano M., Li X. L. Monochromatic and heterochromatic subgraphs in edge-colored graphs—a survey. Graphs Combin, 2008, 24: 237-263

[4] Kostochka A, Yancey M. Large rainbow matchings in edge-colored graphs. Combin Probab Comput (to appear)

[5] LeSaulnier T D, Stocker C, Wenger P S, West D B Rainbow matching in edge-colored graphs. Electron J Combin, 2010, 17: #N26

[6] Li H., Wang G. H. Color degree and heterochromatic matchings in edge-colored bipartite graphs. Util Math, 2008, 77: 145-154

[7] Ryser H J. Neuere probleme der kombinatorik. In: Vortrage uber Kombinatorik Oberwolfach. Mathematisches Forschungsinstitut Oberwolfach, July 1967, 24–29

[8] Stein K. S. Transversals of Latin squares and their generalizations. Pacific J Math, 1975, 59(2): 567-575

[9] Wang G H Rainbow matchings in properly edge colored graphs. Electron J Combin, 2011, 18: #N162

[10] Wang G H, Li H Heterochromatic matchings in edge-colored graphs. Electron J Combin, 2008, 15: #N138

[11] Wanless I. M. Chapman R. Transversals in Latin squares: A survey. Surveys in Combinatorics 2011, 2011, Cambridge: Cambridge University Press, 403-437