Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Properly Coloured Cycles and Paths: Results and Open Problems
verfasst von : Gregory Gutin, Eun Jung Kim
Erschienen in: Graph Theory, Computational Intelligence and Thought
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.