  In an edge-colored graph, a traversal cost occurs at a vertex along a path
when consecutive edges with different colors are traversed. The value of the
traversal cost depends only on the colors of the traversed edges. This concept
leads to two global cost measures, namely the \emph{reload cost} and the
\emph{changeover cost}, that have been studied in the literature and have
various applications in telecommunications, transportation networks, and energy
distribution networks. Previous work focused on problems with an edge-colored
graph being part of the input. In this paper, we formulate and focus on two
pairs of problems that aim to find an edge coloring of a graph so as to
minimize the reload and changeover costs. The first pair of problems aims to
find a proper edge coloring so that the reload/changeover cost of a set of
paths is minimized. The second pair of problems aim to find a proper edge
coloring and a spanning tree so that the reload/changeover cost is minimized.
We present several hardness results as well as polynomial-time solvable special
cases.
