\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Guanghui Wang and Hao Li}
%
%
\medskip
\noindent
%
%
{\bf Heterochromatic Matchings in Edge-Colored Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
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.



\bye