The heterochromatic matchings in edge-colored bipartite graphs.
Hao Li, Xueliang Li, Guizhen Liu, Guanghui Wang · 2009
Let (G,C) be an edge-colored bipartite graph with bi-partition (X, Y). A heterochromatic matching of G is such a matching in which no two edges have the same color. Let N(c)(S) denote a maximum color neighborhood of S subset of V(G). We show that if |N(c)(S)| >= |S| for all S subset of X, then G has a heterochromatic matching with cardinality at least inverted right perpendicular |X|/3 inverted left perpendicular. We also obtain that if |X| = |Y| = n and |N(c)(S)| >= |S| for all S subset of X or S subset of Y, then G has a heterochromatic matching with cardinality at least inverted right perpendicular 3n/8 inverted left perpendicular