  We give a randomized algorithm that properly colors the vertices of a
triangle-free graph G on n vertices using O(\Delta(G)/ log \Delta(G)) colors,
where \Delta(G) is the maximum degree of G. The algorithm takes
O(n\Delta2(G)log\Delta(G)) time and succeeds with high probability, provided
\Delta(G) is greater than log^{1+{\epsilon}}n for a positive constant
{\epsilon}. The number of colors is best possible up to a constant factor for
triangle-free graphs. As a result this gives an algorithmic proof for a sharp
upper bound of the chromatic number of a triangle-free graph, the existence of
which was previously established by Kim and Johansson respectively.
