  We consider coloring problems in the distributed message-passing setting. The
previously-known deterministic algorithms for edge-coloring employed at least
(2Delta - 1) colors, even though any graph admits an edge-coloring with Delta +
1 colors [V64]. Moreover, the previously-known deterministic algorithms that
employed at most O(Delta) colors required superlogarithmic time
[B15,BE10,BE11,FHK15]. In the current paper we devise deterministic
edge-coloring algorithms that employ only Delta + o(Delta) colors, for a very
wide family of graphs. Specifically, as long as the arboricity is a =
O(Delta^{1 - \epsilon}), for a constant epsilon > 0, our algorithm computes
such a coloring within {polylogarithmic} deterministic time. We also devise
significantly improved deterministic edge-coloring algorithms for {general
graphs} for a very wide range of parameters. Specifically, for any value $\chi$
in the range [4Delta, 2^{o(log Delta)} \cdot Delta], our \chi-edge-coloring
algorithm has smaller running time than the best previously-known
\chi-edge-coloring algorithms. Our algorithms are actually much more general,
since edge-coloring is equivalent to {vertex-coloring of line graphs.} Our
method is applicable to vertex-coloring of the family of graphs with {bounded
diversity} that contains line graphs, line graphs of hypergraphs, and many
other graphs.
  Our results are obtained using a novel technique that connects vertices or
edges in a certain way that reduces clique size. The resulting structures,
which we call {connectors}, can be colored more efficiently than the original
graph. Moreover, the color classes constitute simpler subgraphs that can be
colored even more efficiently using appropriate connectors. Hence, we recurse
until we obtain sufficiently simple structures that are colored directly. We
introduce several types of connectors that are useful for various scenarios.
