
To our knowledge, no linear time algorithm for finding properly colored
cycles appears in the literature. (A slightly worse than linear
algorithm is proposed in [1]}.)
We repair this omission in this section, by a mostly straightforward
adaptation of the reduction for paths in [2]} – the
main subtlety being that we need to tweak the definition of
P-gadgets for our purpose.

We generalize the reduction for the 2-edge-colored case to cover
edge-colored graphs with chromatic degree \(\le 2\) , and unify it with the
well-known correspondence between bipartite matchings and directed graphs.
This is achieved by extending it to a combinatorial bijection between graphs
equipped with perfect matchings and a new object we call locally
2-colored graphs.

