OJDM  Vol.2 No.2 , April 2012
Rainbow Matchings in Properly Colored Bipartite Graphs
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 .
Cite this paper: 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.

[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.