Properly Coloured Cycles and Paths: Results and Open Problems
Properly Coloured Cycles and Paths: Results and Open Problems
复制标题
DOI：
10.1007/978-3-642-02029-2_19
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
G. Gutin;Eun Jung Kim
中科院分区：
文献类型：
--
作者：
G. Gutin;Eun Jung Kim
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 multigraphGinto an ordinary graph that allow us to check the existence of PC cycles and PC (s,t)-paths inGand, 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.
