\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 Yair Caro, Arie Lev, Yehuda Roditty, Zsolt Tuza and Raphael Yuster}
%
%
\medskip
\noindent
%
%
{\bf On Rainbow Connection}
%
%
\vskip 5mm
\noindent
%
%
%
%
An edge-colored graph $G$ is {\em rainbow connected} if any two
vertices are connected by a path whose edges have distinct colors.
The {\em rainbow connection number} of a connected graph $G$, denoted
$rc(G)$, is the smallest number of colors that are needed in order to
make $G$ rainbow connected. In this paper we prove several non-trivial
upper bounds for $rc(G)$, as well as determine sufficient conditions
that guarantee $rc(G)=2$.  Among our results we prove that if $G$ is a
connected graph with $n$ vertices and with minimum degree $3$ then
$rc(G) < 5n/6$, and if the minimum degree is $\delta$ then $rc(G) \le
{\ln \delta\over\delta}n(1+o_\delta(1))$.  We also determine the
threshold function for a random graph to have $rc(G)=2$ and make
several conjectures concerning the computational complexity of rainbow
connection.



\bye

.