Cycles and paths in edge‐colored graphs with given degrees
- 20 October 2009
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 64 (1) , 63-86
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, 2010Keywords
This publication has 11 references indexed in Scilit:
- Characterization of edge‐colored complete graphs with properly colored Hamilton pathsJournal of Graph Theory, 2006
- Properly colored Hamilton cycles in edge-colored complete graphsRandom Structures & Algorithms, 1997
- Alternating cycles and paths in edge-coloured multigraphs: A surveyDiscrete Mathematics, 1997
- Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RPCombinatorics, Probability and Computing, 1996
- Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity resultsRAIRO - Operations Research, 1996
- DNA physical mapping and alternating Eulerian cycles in colored graphsAlgorithmica, 1995
- Graph folding and programmable logic arrayNetworks, 1987
- Fast probabilistic algorithms for hamiltonian circuits and matchingsJournal of Computer and System Sciences, 1979
- Alternating Hamiltonian cyclesIsrael Journal of Mathematics, 1976
- Some Theorems on Abstract GraphsProceedings of the London Mathematical Society, 1952