On s-t paths and trails in edge-colored graphs

DOI10.1016/j.endm.2009.11.037zbMath1268.05112OpenAlexW1988399927MaRDI QIDQ2840541

Fábio Protti, Adria Lyra, Jérôme Monnot, Laurent Gourvès, Carlos A. Martinhon

Publication date: 19 July 2013

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

Full work available at URL: https://doi.org/10.1016/j.endm.2009.11.037

zbMATH Keywords

Hamiltonian path problemmonochromatic pathsedge-colored graphsproperly edge-colored pathsEulerian trail problemproperly edge-colored trails

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Unnamed Item ⋮ Paths and trails in edge-colored weighted graphs

Cites Work

• Unnamed Item
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• On monochromatic paths in edge-coloured digraphs
• Alternating Eulerian trails with prescribed degrees in two edge-colored complete graphs
• A note on alternating cycles in edge-coloured graphs
• Alternating cycles and paths in edge-coloured multigraphs: A survey
• Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
• Alternating paths in edge-colored complete graphs
• Finding paths in graphs avoiding forbidden transitions
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Paths and trails in edge-colored graphs
• The complexity of finding maximum disjoint paths with length constraints
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results

This page was built for publication: On s-t paths and trails in edge-colored graphs