  Given a graph $G$, an edge-coloring is an assignment of colors to edges of
$G$ such that any two edges sharing an endpoint receive different colors. By
Vizing's celebrated theorem, any graph of maximum degree $\Delta$ needs at
least $\Delta$ and at most $(\Delta + 1)$ colors to be properly edge colored.
In this paper, we study edge colorings in the streaming setting. The edges
arrive one by one in an arbitrary order. The algorithm takes a single pass over
the input and must output a solution using a much smaller space than the input
size. Since the output of edge coloring is as large as its input, the assigned
colors should also be reported in a streaming fashion.
  The streaming edge coloring problem has been studied in a series of works
over the past few years. The main challenge is that the algorithm cannot
"remember" all the color assignments that it returns. To ensure the validity of
the solution, existing algorithms use many more colors than Vizing's bound.
Namely, in $n$-vertex graphs, the state-of-the-art algorithm with
$\widetilde{O}(n s)$ space requires $O(\Delta^2/s + \Delta)$ colors. Note, in
particular, that for an asymptotically optimal $O(\Delta)$ coloring, this
algorithm requires $\Omega(n\Delta)$ space which is as large as the input.
Whether such a coloring can be achieved with sublinear space has been left
open.
  In this paper, we answer this question in the affirmative. We present a
randomized algorithm that returns an asymptotically optimal $O(\Delta)$ edge
coloring using $\widetilde{O}(n \sqrt{\Delta})$ space. More generally, our
algorithm returns a proper $O(\Delta^{1.5}/s + \Delta)$ edge coloring with
$\widetilde{O}(n s)$ space, improving prior algorithms for the whole range of
$s$.
