  We investigate the computational complexity of the following problem. We are
given a graph in which each vertex has an initial and a target color. Each pair
of adjacent vertices can swap their current colors. Our goal is to perform the
minimum number of swaps so that the current and target colors agree at each
vertex. When the colors are chosen from {1,2,...,c}, we call this problem
c-Colored Token Swapping since the current color of a vertex can be seen as a
colored token placed on the vertex. We show that c-Colored Token Swapping is
NP-complete for c = 3 even if input graphs are restricted to connected planar
bipartite graphs of maximum degree 3. We then show that 2-Colored Token
Swapping can be solved in polynomial time for general graphs and in linear time
for trees. Besides, we show that, the problem for complete graphs is
fixed-parameter tractable when parameterized by the number of colors, while it
is known to be NP-complete when the number of colors is unbounded.
