06.05.2009

Sufficient degree conditions for the existence of properly edge-colored cycles and paths in edge-colored graphs, multigraphs and random graphs are inverstigated. 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.