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

DOI10.1016/S0012-365X(96)00160-4zbMath0876.05057WikidataQ126988123 ScholiaQ126988123MaRDI QIDQ1356728

Gregory Gutin, Jörgen Bang-Jensen

Publication date: 25 November 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Hamiltonicitymultidigraphsalternating cyclesalternating pathsedge-coloured multigraph

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45)

Related Items (42)

On the tractability of shortest path problems in weighted edge-coloured graphs ⋮ Paths and trails in edge-colored graphs ⋮ A note on alternating cycles in edge-coloured graphs ⋮ Proper Hamiltonian cycles in edge-colored multigraphs ⋮ Alternating-pancyclism in 2-edge-colored graphs ⋮ Proper Hamiltonian paths in edge-coloured multigraphs ⋮ Properly coloured Hamiltonian paths in edge-coloured complete graphs ⋮ Properly colored 2-factors of edge-colored complete bipartite graphs ⋮ A generalization of properly colored paths and cycles in edge-colored graphs ⋮ Alternating kernels ⋮ Proper cycles and rainbow cycles in 2-triangle-free edge-colored complete graphs ⋮ Properly colored cycles in edge-colored 2-colored-triangle-free complete graphs ⋮ Parallel connectivity in edge-colored complete graphs: complexity results ⋮ Unbalanced spanning subgraphs in edge labeled complete graphs ⋮ Proper connection of graphs ⋮ Properly colored paths and cycles ⋮ Long properly colored cycles in edge colored complete graphs ⋮ Networks, frictions, and price dispersion ⋮ Unnamed Item ⋮ Fork-forests in bi-colored complete bipartite graphs ⋮ On the number of alternating paths in random graphs ⋮ Symbolic coloured SCC decomposition ⋮ A note on equitable Hamiltonian cycles ⋮ Unnamed Item ⋮ A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs ⋮ On the number of alternating paths in bipartite complete graphs ⋮ Cycles and paths in edge‐colored graphs with given degrees ⋮ Unnamed Item ⋮ Paths and Trails in Edge-Colored Graphs ⋮ On the (di)graphs with (directed) proper connection number two ⋮ A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem ⋮ On supereulerian 2-edge-coloured graphs ⋮ Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic triangles ⋮ Properly Coloured Cycles and Paths: Results and Open Problems ⋮ On s-t paths and trails in edge-colored graphs ⋮ Vertex alternating-pancyclism in 2-edge-colored generalized sums of graphs ⋮ Color degree and alternating cycles in edge-colored graphs ⋮ Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs ⋮ Note on alternating directed cycles ⋮ Paths and trails in edge-colored weighted graphs ⋮ Monochromatic-degree conditions for properly colored cycles in edge-colored complete graphs ⋮ Extensions of results on rainbow Hamilton cycles in uniform hypergraphs

Cites Work

• Cycles and paths of many lengths in bipartite digraphs
• Cycles in bipartite tournaments
• Alternating cycles in edge-partitioned graphs
• Alternating Eulerian trails with prescribed degrees in two edge-colored complete graphs
• Alternating Hamiltonian circuits in edge-coloured bipartite graphs
• Eulerian graphs and related topics. Part 1, Volume 1
• Julius Petersen's theory of regular graphs
• Graphs with cycles having adjacent lines different colors
• Alternating Hamiltonian cycles
• A property of the colored complete graph
• On cycles in multipartite tournaments
• Hamiltonian circuits determining the order of chromosomes
• A note on alternating cycles in edge-coloured graphs
• Properly coloured Hamiltonian paths in edge-coloured complete graphs
• Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
• Cycles and paths in bipartite tournaments with spanning configurations
• Alternating paths in edge-colored complete graphs
• Graphs with Hamiltonian cycles having adjacent lines different colours
• Weakly hamiltonian-connected vertices in bipartite tournaments
• Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs
• 1-Faktoren von Graphen. (1-factors of graphs)
• A note concerning graphs with unique f-factors
• Polynomial Algorithms for Finding Cycles and Paths in Bipartite Tournaments
• Alternating cycles in edge-colored graphs
• Cycles in digraphs– a survey
• Alternating hamiltonian cycles in two colored complete bipartite graphs
• Finding a Longest Path in a Complete Multipartite Digraph
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
• Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey
• On the 1-factors of a non-separable graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Alternating cycles and paths in edge-coloured multigraphs: A survey