Cycles and paths in edge‐colored graphs with given degrees |
| |
| Authors: | A. Abouelaoualim K. Ch. Das W. Fernandez de la Vega M. Karpinski Y. Manoussakis C. A. Martinhon R. Saad |
| |
| Affiliation: | 1. L.R.I., BT. 490, Université de Paris‐Sud, 91405 Orsay Cedex, France;2. Department of Computer Science, University of Bonn, 53117 Bonn, Germany;3. Institute of Computation, Fluminense Federal University, RJ 24210‐240, Brazil;4. RMC Saint‐Jean, Edifice Lahaie, 15 Jacques Cartier Nord, Saint‐Jean‐Sur‐Richelieu (QC), J3B 8R8 Canada |
| |
| Abstract: | 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 |
| |
| Keywords: | edge‐colored graph cycle path properly edge‐colored hamiltonian |
|
|
