Color Degree and Color Neighborhood Condition for Large Heterochromatic Matchings in Edge-Colored Bipartite Graphs

Lin Hu and Xueliang Li
Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, P. R. China


Abstract     Full Text  PDF

Let $G = (V;E)$ be an edge-colored graph, i.e., G is assigned a surjective function $C : E \rightarrow \{1,2;\cdots r\}, the set of colors. A matching of G is called heterochromatic if its any two edges have different colors. Let (B;C) be an edgecolored bipartite graph and dc(v) be color degree of a vertex v. We show that if d^{c}(v)\geq k for every vertex $v$ of B, then B has a heterochromatic matching of cardinality at least k-1. Let $N^{c}(S)$ denote a maximum color neighborhood of $S \subseteq V(B)$. We also show that if for all $S\subseteq X$, then $B$ contains a heterochromatic matching with cardinality at least $\lceil\frac{|X|}{2}\rceil$.