×

The heterochromatic matchings in edge-colored bipartite graphs. (English) Zbl 1224.05411

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 \).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite