2008/05/26 by Gregory Gutin, Eun Jung Kim, Eun‐Jung Kim +2
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #cs.DM #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.0805.3901
openalex publication_date 2008/05/26 · arxiv created 2008/05/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we consider a number of results and seven conjectures on properly edge-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 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.