Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2009 Copyright 2009 Universität Bonn, Institut für Informatik, Abt. V


Cycles and Paths in Edge-Colored Graphs with Given Degrees
A. Abouelaoualim, Kinkar Chandra Das, Wenceslas Fernandez de la Vega,
Marek Karpinski, Yannis Manoussakis, Carlos A. Martinhon and Rachid Saad
[Download PostScript] [Download PDF]

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.

Last Change: 05/06/09 at 09:37:19
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope