Frontiers of Mathematics in China >

2012 , Vol. 7 >Issue 3: 543 - 550

DOI: https://doi.org/10.1007/s11464-012-0202-9

RESEARCH ARTICLE

Existence of rainbow matchings in properly edge-colored graphs

  • Guanghui WANG , 1 ,
  • Jianghua ZHANG 2 ,
  • Guizhen LIU 1
Expand
  • 1. School of Mathematics, Shandong University, Jinan 250100, China
  • 2. School of Management, Shandong University, Jinan 250100, China

Received date: 29 Aug 2011

Accepted date: 18 Feb 2012

Published date: 01 Jun 2012

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg
Fold

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)|>(δ2+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|}>(δ2+4δ-4)/4, then G has a rainbow matching of size δ.

Key words： Rainbow matching; properly edge-colored graph

Cite this article

Guanghui WANG , Jianghua ZHANG , Guizhen LIU . Existence of rainbow matchings in properly edge-colored graphs[J]. Frontiers of Mathematics in China, 2012 , 7(3) : 543 -550 . DOI: 10.1007/s11464-012-0202-9

References

Publishing order | Descend order by publishing year | Descend order by cited within
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

DOI

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

Options
Outlines

/

〈 〉