Voir la notice de l'article provenant de la source Numdam
We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that s consecutive edges are in one color and t consecutive edges are in another color.
Nous étudions le problème de trouver dans un graphe arêtes-coloré une chaîne alternée joignant deux sommets donnés et passant par des sommets donnés (une chaîne est alternée si deux arêtes adjacentes arbitraires ont des couleurs différentes). Plus précisément nous démontrons que ce problème est NPcomplet dans le cas de graphes 2-arêtes-colorés. Ensuite nous montrons que le problème de l'existence d'une telle chaîne est polynomial dans le cas où l'on se restreint aux graphes complets 2-arêtes-colorés. Nous étudions également le problème de trouver une (s,t)-chaîne (c'est-à-dire une chaîne de longueur s+t qui se partage en deux sous-chaînes monochromatiques de couleurs différentes) joignant deux sommets donnés et passant par des sommets donnés, dans un graphe complet arêtes-coloré.
@article{MSH_1994__127__49_0,
author = {Chou, W. S. and Manoussakis, Y. and Megalakaki, O. and Spyratos, M. and Tuza, Zs.},
title = {Paths through fixed vertices in edge-colored graphs},
journal = {Math\'ematiques informatique et sciences humaines},
pages = {49--58},
publisher = {Ecole des hautes-\'etudes en sciences sociales},
volume = {127},
year = {1994},
mrnumber = {1324227},
zbl = {0826.68064},
language = {en},
url = {http://geodesic.mathdoc.fr/item/MSH_1994__127__49_0/}
}
TY - JOUR AU - Chou, W. S. AU - Manoussakis, Y. AU - Megalakaki, O. AU - Spyratos, M. AU - Tuza, Zs. TI - Paths through fixed vertices in edge-colored graphs JO - Mathématiques informatique et sciences humaines PY - 1994 SP - 49 EP - 58 VL - 127 PB - Ecole des hautes-études en sciences sociales UR - http://geodesic.mathdoc.fr/item/MSH_1994__127__49_0/ LA - en ID - MSH_1994__127__49_0 ER -
%0 Journal Article %A Chou, W. S. %A Manoussakis, Y. %A Megalakaki, O. %A Spyratos, M. %A Tuza, Zs. %T Paths through fixed vertices in edge-colored graphs %J Mathématiques informatique et sciences humaines %D 1994 %P 49-58 %V 127 %I Ecole des hautes-études en sciences sociales %U http://geodesic.mathdoc.fr/item/MSH_1994__127__49_0/ %G en %F MSH_1994__127__49_0
Chou, W. S.; Manoussakis, Y.; Megalakaki, O.; Spyratos, M.; Tuza, Zs. Paths through fixed vertices in edge-colored graphs. Mathématiques informatique et sciences humaines, Tome 127 (1994), pp. 49-58. http://geodesic.mathdoc.fr/item/MSH_1994__127__49_0/