Sufficient degree conditions for the existence of properly edge-colored cycles and paths in edge-colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge-colored multigraph of order n on at least three colors and with minimum colored degree greater than or equal to ⌈(n+1)-2⌉ has properly edge-colored cycles of all possible lengths, including hamiltonian cycles. Longest properly edge-colored paths and hamiltonian paths between given vertices are considered as well. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 63–86, 2010
['A. Abouelaoualim', 'K. Ch. Das', 'W. Fernandez de la Vega', 'Marek Karpinski', 'Yannis Manoussakis', 'Carlos A. J. Martinhon', 'Ram Al Jaffri Saad']
Cycles and paths in edge-colored graphs with given degrees