Properly Coloured Cycles and Paths: Results and Open Problems

摘要

In this paper, we consider a number of results and six conjectures on properly coloured (PC) paths and cycles in edge-coloured multigraphs. We overview some known results and prove new ones. In particular, we consider a family of transformations of an edge-coloured multigraph G into an ordinary graph that allow us to check the existence of PC cycles and PC (s, t)-paths in G and, if they exist, to find shortest ones among them. We raise a problem of finding the optimal transformation and consider a possible solution to the problem.