Heterochromatic matchings in edge-colored graphs (Q1010874)

Summary: Let \(G\) be an (edge-)colored graph. A heterochromatic matching of \(G\) is a matching in which no two edges have the same color. For a vertex \(v\), let \(d^c(v)\) be the color degree of \(v\). We show that if \(d^c(v)\geq k\) for every vertex \(v\) of \(G\), then \(G\) has a heterochromatic matching of size \(\big\lceil{5k-3\over 12}\big\rceil\). For a colored bipartite graph with bipartition \((X,Y)\), we prove that if it satisfies a Hall-like condition, then it has a heterochromatic matching of cardinality \(\big\lceil{|X|\over 2}\big\rceil\), and we show that this bound is best possible.