Alternating cycles and paths in edge-coloured multigraphs: A survey (Q1356728)

A path or a cycle in an edge-coloured multigraph is called alternating if any two consecutive edges have different colours. The authors give a survey of results about alternating paths and cycles by considering both aspects, the theoretical and the algorithmic one. Several results are based on the theory of directed paths and cycles in multidigraphs since we often have a simple relation between certain edge-coloured multigraphs and multidigraphs. For instance, there is a natural correspondence between alternating paths and cycles in a bipartite 2-edge-coloured multigraph \(G\) and directed paths and cycles in a bipartite multidigraph obtained from \(G\) by orienting the edges between the bipartition classes depending on their colours. One chapter of the paper deals with the construction of alternating cycles and of alternating paths between given vertices in arbitrary edge-coloured multigraphs. In the other chapters, the authors mainly consider complete and complete bipartite multigraphs. Of special interest are the 2-edge-coloured ones since for that kind of graphs, several problems which are intractable in general become tractable such as the problem of Hamiltonicity (i.e. the existence of an alternating Hamiltonian cycle), the problem of even-pancyclicity (i.e. the existence of alternating cycles of any even length), and the problem of constructing a longest alternating path or cycle. For 2-edge-coloured complete (bipartite) graphs, the authors present characterizations of the Hamiltonian and the even-pancyclic ones and they give polynomial algorithms for constructing longest alternating paths and cycles. If we allow more than 2 colours, then the complexities of that problems could not be completely determined so far. The authors present some approaches and a survey of some partial results for that case.