  We develop sequential algorithms for constructing edge-colorings of graphs
and multigraphs efficiently and using few colors. Our primary focus is
edge-coloring arbitrary simple graphs using $d+1$ colors, where $d$ is the
largest vertex degree in the graph. Vizing's Theorem states that every simple
graph can be edge-colored using $d+1$ colors. Although some graphs can be
edge-colored using only $d$ colors, it is NP-hard to recognize graphs of this
type [Holyer, 1981]. So using $d+1$ colors is a natural goal. Efficient
techniques for $(d+1)$-edge-coloring were developed by Gabow, Nishizeki, Kariv,
Leven, and Terada in 1985, and independently by Arjomandi in 1982, leading to
algorithms that run in $O(|E| \sqrt{|V| \log |V|})$ time. They have remained
the fastest known algorithms for this task.
  We improve the runtime to $O(|E| \sqrt{|V|})$ with a small modification and
careful analysis. We then develop a randomized version of the algorithm that is
much simpler to implement and has the same asymptotic runtime, with very high
probability. On the way to these results, we give a simple algorithm for
$(2d-1)$-edge-coloring of multigraphs that runs in $O(|E|\log d)$ time.
Underlying these algorithms is a general edge-coloring strategy which may lend
itself to further applications.
