Paths and trails in edge-colored graphs

DOI10.1016/j.tcs.2008.09.021zbMath1155.68053OpenAlexW2116339599MaRDI QIDQ2378531

Yanyan Li

Publication date: 8 January 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.021

zbMATH Keywords

connectivityedge-colored graphsproperly edge-colored pathstrails and cycles

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (17)

Acyclicity in edge-colored graphs ⋮ Proper vertex-pancyclicity of edge-colored complete graphs without joint monochromatic triangles ⋮ Nonlinear large deviations: beyond the hypercube ⋮ Parallel connectivity in edge-colored complete graphs: complexity results ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Unnamed Item ⋮ The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles ⋮ Optimal pathway reconstruction on 3D NMR maps ⋮ A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs ⋮ Theory and implementation of coalitional analysis in cooperative decision making ⋮ The Minimum Reload s-t Path/Trail/Walk Problems ⋮ The minimum reload \(s-t\) path, trail and walk problems ⋮ Using matrices to link conflict evolution and resolution in a graph model ⋮ Maximum colored trees in edge-colored graphs ⋮ On s-t paths and trails in edge-colored graphs ⋮ Acyclic Digraphs ⋮ Paths and trails in edge-colored weighted graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The directed subgraph homeomorphism problem
• Alternating cycles in edge-partitioned graphs
• Alternating Hamiltonian cycles
• Hamiltonian circuits determining the order of chromosomes
• 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
• The number of 2-edge-colored complete graphs with unique Hamiltonian alternating cycle
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Characterization of edge-colored complete graphs with properly colored Hamilton paths
• Graph folding and programmable logic array
• On the Computational Complexity of Combinatorial Problems
• Faster scaling algorithms for general graph matching problems
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: Paths and trails in edge-colored graphs