HAMILTONIAN PROBLEMS IN EDGE-COLORED COMPLETE GRAPHS AND EULERIAN CYCLES IN EDGE-COLORED GRAPHS: SOME COMPLEXITY RESULTS

摘要

Dans un graphe arêtes-coloré, on dit qu'un chemin (cycle) est alternant s'il est au moins de longueur 2 (3) et si toute paire d'arêtes adjacentes de ce chemin (cycle) sont de couleurs différentes. Nous donnons des algorithmes efficaces trouvant des facteurs alternants comportant un nombre minimum de cycles et, en utilisant ce résultat, nous obtenons des algorithmes polynomiaux pour la recherche de cycles et chemins hamiltoniens alternants dans des graphes complets 2-arêtes-colorés. . Nous montrons ensuite que certaines extensions de ces résultats aux graphes complets k-arêtes-colorés, k ≥ 3 sont NP-complets. D'autres problèmes similaires sont proposés. Enfin, nous donnons une caractérisation polynomiale de l'existence de cycles eulériens alternants dans des graphes arêtes-colorés. Nous donnons une preuve algorithmique (constructive) qui utilise une procédure trouvant un couplage parfait dans un graphe k-parties complet.%In an edge-colored, we say that a path (cycle) is alternating if it has length at least 2 (3) and if any 2 adjacent edges of this path (cycle) have different colors. We give efficient algorithms for finding alternating factors with a minimum number of cycles and then, by using this result, we obtain polynomial algorithms for finding alternating Hamiltonian cycles and paths in 2-edge-colored complete graphs. We then show that some extensions of these results to k-edge-colored complete graphs, k ? 3, are NP-complete. related problems are proposed. Finally, we give a polynomial characterization of the existence of alternating Eulerian cycles in edge-colored graphs. Our proof is algorithmic and uses a procedure that finds a perfect matching in a complete k-partite graph.