Color degree and heterochromatic matchings in edge-colored bipartite graphs - Li, Hao; Wang, Guanghui (Utilitas Mathematica, 2008)
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 dc(v) ≥ k ≥ 3 for every vertex v of G, then G has a heterochromatic matching with cardinality at least [2k/3].