Li, Hao; Li, Xueliang; Liu, Guizhen; Wang, Guanghui The heterochromatic matchings in edge-colored bipartite graphs. (English) Zbl 1224.05411 Ars Comb. 93, 129-139 (2009). Summary: 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\subseteq V(G)\). We show that, if \(| N^{c}(S)| \geq | S| \) for all \(S\subseteq X\), then \(g\) has a heterochromatic matching with cardinality as least \(\lceil | X| /3\rceil \). We also obtain that if \(| X| =| Y| =n\) and \(| N^{c}(S)| \geq | S| \) for all \(S\subseteq X\) or \(S\subseteq Y\), then \(G\) has a heterochromatic matching with cardinality at least \(\lceil 3n/8\rceil \). Cited in 5 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:bipartite graph; heterochromatic matching; colour neighborhood PDFBibTeX XMLCite \textit{H. Li} et al., Ars Comb. 93, 129--139 (2009; Zbl 1224.05411)