Characterization of edge-colored complete graphs with properly colored Hamilton paths

DOI10.1002/jgt.20188zbMath1125.05037OpenAlexW4231579672MaRDI QIDQ3418198

Arash Rafiey, Jinfeng Feng, Hans-Erik Giesen, Gregory Gutin, Yubao Guo, Tommy R. Jensen

Publication date: 2 February 2007

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20188

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45)

Related Items (13)

Paths and trails in edge-colored graphs ⋮ Proper Hamiltonian cycles in edge-colored multigraphs ⋮ Maximum properly colored trees in edge-colored graphs ⋮ Proper Hamiltonian paths in edge-coloured multigraphs ⋮ Properly coloured Hamiltonian cycles in edge-coloured complete graphs ⋮ Properly colored 2-factors of edge-colored complete bipartite graphs ⋮ Sufficient conditions for the existence of spanning colored trees in edge-colored graphs ⋮ Long properly colored cycles in edge colored complete graphs ⋮ A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs ⋮ Cycles and paths in edge‐colored graphs with given degrees ⋮ Properly colored spanning trees in edge-colored graphs ⋮ Paths and Trails in Edge-Colored Graphs ⋮ Properly Coloured Cycles and Paths: Results and Open Problems

Cites Work

• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP

This page was built for publication: Characterization of edge-colored complete graphs with properly colored Hamilton paths