Color degree and heterochromatic matchings in edge-colored bipartite graphs

Abstract

Let (G, C) be an (edge-)colored bipartite graph. A heterochromatic matching of G is such a matching in which no two edges have the same color. Let d ^c(v), named the color degree of a vertex v, be defined as the maximum number of edges adjacent to v, that have distinct colors. We show that if d^c(v) ≥ k ≥ 3 for every vertex v of G, then G has a heterochromatic matching with cardinality at least [2k/3].