﻿Rainbow Matchings in Properly Colored Bipartite Graphs

Open Journal of Discrete Mathematics
Vol.2 No.2(2012), Article ID:18869,3 pages DOI:10.4236/ojdm.2012.22011

Rainbow Matchings in Properly Colored Bipartite Graphs

Guanghui Wang, Guizhen Liu

School of Mathematics, Shandong University, Jinan, China

Email: {ghwang, gzliu}@sdu.edu.cn

Received January 19, 2012; revised February 16, 2012; accepted March 25, 2012

Keywords: rainbow matching; 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.

1. Introduction and Notation

We use [1] for terminology and notations not defined here and consider simple undirected graphs only. Let be a graph. A proper edge-coloring of G is a function (is the set of non-negative integers) such that any two adjacent edges have distinct colors. If G is assigned such a coloring c, then we say that G is a properly edge-colored graph, or simply a properly colored graph. Let denote the color of the edge. For a subgraph H of G, let

.

A subgraph H of G is called rainbow if its edges have distinct colors. Recently rainbow subgraphs have received much attention, see the survey paper [2]. Here we are interested in rainbow matchings. The study of rainbow matchings began with the following conjectures.

Conjecture 1. (Ryser [3,4]) Every Latin square of odd order has a Latin transversal.

Conjecture 2. (Stein [5]) Every Latin square of order n has a partial Latin transversal of size at least.

An equivalent statement is that every proper n-edgecoloring of the complete bipartite graph contains a rainbow matching of size Moreover, if n is odd, there exists a rainbow perfect matching. Hatami and Shor [6] proved that there is always a partial Latin transversal (rainbow matching) of size at least.

Another topic related to rainbow matchings is orthogonal matchings of graphs. Let G be a graph on n vertices which is an edge disjoint union of m k-factors (i.e. k regular spanning subgraphs). We ask if there is a matching M of m edges with exactly one edge from each k-factor? Such a matching is called orthogonal because of applications in design theory. A matching M is suborthogonal if there is at most one edge from each k-factor. Alspach [7] posed the above problem in the case. Stong [8] proved that if, then there is a such orthogonal matching. For, the answer is yes, see [9]. In the same paper, Anstee and Caccetta proved the following theorem when.

Theorem 3. [9] Let G be an m-regular graph on n vertices. Then for any decomposition of into m 1-factors, there is a matching M of p edges, at most one edge from each 1-factor, with

In any decomposition of into m k-factors, we can construct an edge colored graph by giving each kfactor a color. Then a rainbow matching of G corresponds to a suborthogonal matching of G. In particular, when, the edge colored graph obtained above is properly colored. So we can pose a more general problem: Let G be a properly colored graph of minimum degree. Is there a rainbow matching of size? Unfortunately, the answer is negative, see [10]. Moreover, if G is a properly colored complete graph, then G has no rainbow matching of size more than. In addition, the following theorem was shown in [11].

Theorem 4. [8] Let G be a properly colored graph, , and. Then G contains a rainbow matching of size.

However, we believe that if the order of a properly colored graph G is much larger than its minimum degree, there should be a rainbow matching of size. In [10], we propose the following problem.

Problem 5. [10] Is there a function such that for each properly colored graph G with , G must contain a rainbow matching of size?

Since when n is even, an Latin square has no Latin transversal (perfect rainbow matching) (see [3]), if the function exists, should be greater than 2n. Motivated by this problem, we prove the following results in [10].

Theorem 6. [10] Let G be a properly colored graph and. Then G has a rainbow matching of size at least.

Theorem 7. [10] Let G be a properly colored trianglefree graph. Then G has a rainbow matching of size at least.

In [12], Wang, Zhang and Liu proved that ifthen G has a rainbow matching of size, which answers the above question in the affirmative. Eiemunsch et al. [13] improved this bound to. Later, this bound was improved to by Lo in [14].

In this paper, we consider the rainbow matching of the properly colored bipartite graph, and prove the following result.

Theorem 8. Let G be a properly colored bipartite graph with bipartition and. If , then G has a rainbow coloring of size at least.

For more result about rainbow matchings under the color degree conditions, we refer to [15,16].

2. Proof of Theorem 8

Let. Without loss of generality, we assume that. Suppose that our conclusion is not true, we choose a maximum rainbow matching M. Let. Without loss of generality, we assume that

.

Then Let and Put and. Let denote the vertices in X which are incident with by three edges with new colors. Clearly,. Otherwise, we can get a rainbow matching of size at least, which is a contradiction. Let denote the vertices which are incident with the vertices in by the edges in M. We have the following claim.

Claim 1..

Proof. Let. If there is an edge such that, then. Otherwise, there is a rainbow matching of size, which is a contradiction. Let denote the edges which are incident with vertices in and have new colors. Since each vertex in has degree at least,

.

On the other hand,. So we have the following equality

.

Hence

Since, , thus.

Without loss of generality, we assume thatwhere. Let denote the vertex which is incident with by an edge in M.

Claim 2. Let be any vertex in and denote the vertex which is incident with by an edge in M. If is incident with a vertex, then .

Proof. Suppose our conclusion does not hold. First, we know that can not be a new color. Otherwise, since are incident with three edges having new colors, we can choose one edge (say e). Then we can get a new rainbow matching of size by adding and deleting. Thus we will get a contradiction. So we conclude that. Since G is properly colored,. So without loss of generality, we assume that. Moreover, we assume that the edges with new colors are incident with are and. Now we can choose such that and is not incident with y. Hence we have a new rainbow matching by adding and deleting, which is a contradiction.

Claim 3. If there exists an edge such that and, then.

Proof. Suppose, to the contrary,. If is a new color, then clearly there exists a rainbow matching of size. So we assume that. Without loss of generality, we assume that. We can also choose one edge e incident with such that e is not incident with y and is a new color. Then we can also obtain a rainbow matching by adding and deleting, which is a contradiction. This completes the proof of Claim 3.

Let xy be an edge such that and. By Claim 2 and Claim 3,. Let and . Since,.

On the other hand,. Hence . That is, which contradicts with. This completes the whole proof.

3. Acknowledgements

We would like to thank the referee for the careful review and the valuable comments. This research was supported by NSFC Grants (61070230, 11101243), IIFSDU (2009 hw001), RFDP (20100131120017) and SRF for ROCS.

REFERENCES

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 EdgeColoured 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 EdgeColored Graphs,” Electronic Journal of Combinatorics, Vol. 15, 2008, Paper #R138.