Alternating cycles and paths in edge-coloured multigraphs: A survey
type: Item
instance of: scholarly article
title: Alternating cycles and paths in edge-coloured multigraphs: A survey
zbMATH Open document ID: 0876.05057
DOI: 10.1016/S0012-365X(96)00160-4
published in: Discrete Mathematics
publication date: 1997-11-25T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05-02
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1019084
zbMATH Keywords: edge-coloured multigraph
zbMATH Keywords: alternating paths
zbMATH Keywords: multidigraphs
zbMATH Keywords: alternating cycles
zbMATH Keywords: Hamiltonicity
author: Jørgen Bang-Jensen
author: G. Gutin
reviewed by: Andreas Huck
MaRDI profile type: Publication
cites work: Q4358434
cites work: Cycles and paths of many lengths in bipartite digraphs
cites work: Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
cites work: Properly coloured Hamiltonian paths in edge-coloured complete graphs
cites work: Weakly hamiltonian-connected vertices in bipartite tournaments
cites work: Q5545296
cites work: Properly coloured Hamiltonian paths in edge-coloured complete graphs without monochromatic triangles
cites work: Q4187840
cites work: Q3907592
cites work: Cycles in bipartite tournaments
cites work: On the 1-factors of a non-separable graph
cites work: Q4320687
cites work: Cycles in digraphs– a survey
cites work: Alternating Hamiltonian cycles
cites work: Q3097395
cites work: Graphs with Hamiltonian cycles having adjacent lines different colours
cites work: Alternating hamiltonian cycles in two colored complete bipartite graphs
cites work: Q4836076
cites work: Q3968970
cites work: Alternating Eulerian trails with prescribed degrees in two edge-colored complete graphs
cites work: Graphs with cycles having adjacent lines different colors
cites work: Q3786318
cites work: Hamiltonian circuits determining the order of chromosomes
cites work: Eulerian graphs and related topics. Part 1, Volume 1
cites work: Q3266934
cites work: Alternating cycles in edge-partitioned graphs
cites work: Q3744182
cites work: Finding a Longest Path in a Complete Multipartite Digraph
cites work: Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey
cites work: On cycles in multipartite tournaments
cites work: Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs
cites work: Q3912829
cites work: Cycles and paths in bipartite tournaments with spanning configurations
cites work: Alternating Hamiltonian circuits in edge-coloured bipartite graphs
cites work: A note concerning graphs with unique f-factors
cites work: Q5538410
cites work: 1-Faktoren von Graphen. (1-factors of graphs)
cites work: Alternating paths in edge-colored complete graphs
cites work: Polynomial Algorithms for Finding Cycles and Paths in Bipartite Tournaments
cites work: Julius Petersen's theory of regular graphs
cites work: Q4739657
cites work: Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
cites work: Q3916595
cites work: A property of the colored complete graph
cites work: Q3707420
cites work: Alternating cycles in edge-colored graphs
cites work: Q3035307
cites work: A note on alternating cycles in edge-coloured graphs
cites work: Q3344011
Wikidata QID: Q126988123
description: scientific article; zbMATH DE number 1019084