Rainbow Matchings in Properly Colored Bipartite Graphs


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 .

Share and Cite:

G. Wang and G. Liu, "Rainbow Matchings in Properly Colored Bipartite Graphs," Open Journal of Discrete Mathematics, Vol. 2 No. 2, 2012, pp. 62-64. doi: 10.4236/ojdm.2012.22011.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] J. A. Bondy and U. S. R. Murty, “Graph Theory with Applications,” Macmillan Press, New York, 1976.
[2] 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
[3] R. A. Brualdi and H. J. Ryser, “Combinatorial Matrix Theory,” Cambridge University Press, Cambridge, 1991.
[4] H. J. Ryser, “Neuere Probleme der Kombinatorik,” in Vortrage uber Kombinatorik Ober-Wolfach, Mathematisches Forschungsinstitut Oberwolfach, 1967, pp. 24-29.
[5] S. K. Stein, “Transversals of Latin Squares and Their Generalizations,” Pacific Journal of Mathematics, Vol. 59, No. 2, 1975, pp. 567-575.
[6] 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
[7] B. Alspach, “Problem 89,” Discrete Mathematics, Vol. 69, 1988, p. 106.
[8] R. Stong, “Orthogonal Matchings,” Discrete Mathematics, Vol. 256, No. 1-2, 2002, pp. 515-518. doi:10.1016/S0012-365X(01)00315-6
[9] 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
[10] G. Wang, “Rainbow Matchings in Properly Edge Colored Graphs,” The Electronic Journal of Combinatorics, Vol. 18, 2011, Paper #P162.
[11] 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.
[12] 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
[13] 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.
[14] A. Lo, “A Note on Rainbow Matchings in Properly Edge-Coloured Graphs,” Arxiv preprint, arXiv:1108.5273v1, 2011.
[15] H. Li and G. Wang, “Color Degree and Heterochromatic Matchings in Edge-Colored Bipartite Graphs,” Utilitas Mathematica, Vol. 77, 2008, pp. 145-154.
[16] G. Wang and H. Li, “Heterochromatic Matchings in Edge-Colored Graphs,” Electronic Journal of Combinatorics, Vol. 15, 2008, Paper #R138.

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.