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 \left|\mathrm{V}(G)\right|>({\delta }^{\mathrm{2}}+\mathrm{14}\delta +\mathrm{1})/\mathrm{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 \{\left|X\right|,\left|Y\right|\}>({\delta }^{\mathrm{2}}+\mathrm{4}\delta -\mathrm{4})/\mathrm{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. New York: Macmillan Press, 1976

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

[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, <month>July</month>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. Transversals in Latin squares: A survey. In: Chapman R, ed. Surveys in Combinatorics 2011. London Math Soc Lecture Note Series, No 392. Cambridge: Cambridge University Press, 2011, 403-437

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg