Research ArticleOpen AccessGoogle Scholar indexed
Rainbow Matchings in Properly Colored Bipartite Graphs
School of Mathematics, Shandong University, Jinan, China
School of Mathematics, Shandong University, Jinan, China
- 1 School of Mathematics, Shandong University, Jinan, China
- 2 School of Mathematics, Shandong University, Jinan, China
Open Journal of Discrete Mathematics·Volume 02 (2012)·Pages 62–64·Published 26 April 2012·DOI10.4236/ojdm.2012.22011
Copy link · social · email
Abstract
Let G be a properly colored bipartite graph. A rainbow matching of G is such a matching in which no two edges have the same color. Let G be a properly colored bipartite graph with bipartition (X,Y) and . We show that if , then G has a rainbow coloring of size at least .
KeywordsRainbow MatchingBipartite Graphs
- J. A. Bondy and U. S. R. Murty, “Graph Theory with Applications,” Macmillan Press, New York, 1976.
- M. Kano and X. Li, “Monochromatic and Heterochromatic Subgraphs in Edge-Colored Graphsa Survey,” Graphs and Combinatorics, Vol. 24, No. 4, 2008, pp. 237-263. doi:10.1007/s00373-008-0789-5
- R. A. Brualdi and H. J. Ryser, “Combinatorial Matrix Theory,” Cambridge University Press, Cambridge, 1991.
- H. J. Ryser, “Neuere Probleme der Kombinatorik,” in Vortrage uber Kombinatorik Ober-Wolfach, Mathematisches Forschungsinstitut Oberwolfach, 1967, pp. 24-29.
- S. K. Stein, “Transversals of Latin Squares and Their Generalizations,” Pacific Journal of Mathematics, Vol. 59, No. 2, 1975, pp. 567-575.
- P. Hatami and P. W. Shor, “A Lower Bound for the Length of a Partial Transversal in a Latin Square,” Journal of Combinatorial Theory, Series A, Vol. 115, No. 7, 2008, pp. 1103-1113. doi:10.1016/j.jcta.2008.01.002
- B. Alspach, “Problem 89,” Discrete Mathematics, Vol. 69, 1988, p. 106.
- R. Stong, “Orthogonal Matchings,” Discrete Mathematics, Vol. 256, No. 1-2, 2002, pp. 515-518. doi:10.1016/S0012-365X(01)00315-6
- R. P. Anstee and L. Caccetta, “Orthogonal Matchings,” Discrete Mathematics, Vol. 179, No. 1-3, 1998, pp. 37-47. doi:10.1016/S0012-365X(97)00025-3
- G. Wang, “Rainbow Matchings in Properly Edge Colored Graphs,” The Electronic Journal of Combinatorics, Vol. 18, 2011, Paper #P162.
- T. D. LeSaulnier, C. Stocker, P. S. Wenger and D. B. West, “Rainbow Matching in Edge-Colored Graphs,” The Electronic Journal of Combinatorics, Vol. 17, 2010, Paper #N26.
- G. Wang, J. Zhang and G. Liu, “Existence of Rainbow Matchings in Properly Edge-Colored Graphs,” Frontiers of Mathematics in China. doi:10.1007/s11464-012-0202-9
- J. Diemunsch, M. Ferrara, C. Moffatt, F. Pfender and P. S. Wenger, “Rainbow Matchings of Size in Properly Edge-Colored Graphs,” Arxiv Preprint, arXiv: 1108. 2521, 2011.
- A. Lo, “A Note on Rainbow Matchings in Properly Edge-Coloured Graphs,” Arxiv preprint, arXiv:1108.5273v1, 2011.
- H. Li and G. Wang, “Color Degree and Heterochromatic Matchings in Edge-Colored Bipartite Graphs,” Utilitas Mathematica, Vol. 77, 2008, pp. 145-154.
- G. Wang and H. Li, “Heterochromatic Matchings in Edge-Colored Graphs,” Electronic Journal of Combinatorics, Vol. 15, 2008, Paper #R138.