  It is well-known that the Chinese postman problem on undirected and directed
graphs is polynomial-time solvable. We extend this result to edge-colored
multigraphs. Our result is in sharp contrast to the Chinese postman problem on
mixed graphs, i.e., graphs with directed and undirected edges, for which the
problem is NP-hard.
