|
|
|
Existence of rainbow matchings in properly edge-colored graphs |
Guanghui WANG1( ), Jianghua ZHANG2, Guizhen LIU1 |
| 1. School of Mathematics, Shandong University, Jinan 250100, China; 2. School of Management, Shandong University, Jinan 250100, China |
|
|
|
|
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 δ.
|
| Keywords
Rainbow matching
properly edge-colored graph
|
|
Corresponding Author(s):
WANG Guanghui,Email:ghwang@sdu.edu.cn
|
|
Issue Date: 01 June 2012
|
|
| 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: 10.1007/s00373-008-0789-5
|
| 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 , July1967, 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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
