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é.
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.
@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 et Sciences humaines},
volume = {128},
year = {1994},
pages = {49-58},
mrnumber = {1324227},
zbl = {0826.68064},
language = {en},
url = {http://dml.mathdoc.fr/item/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 et Sciences humaines, Tome 128 (1994) pp. 49-58. http://gdmltest.u-ga.fr/item/MSH_1994__127__49_0/
[1] and , Alternating Hamiltonian Circuits in 2-colored Complete Graphs, Theory of Graphs, Akadémiai Kiadô, Budapest (1968) 11-18. | Zbl 0159.54202
[2] , , and , On the Complexity of Some Hamiltonian and Eulerian Problems in Edge-colored Complete Graphs, Lecture Notes in Computer Sciences (W.L. Hsu and R. C. T. Lee Eds) Vol. 557 (1991) 190-198, Springer Verlag (also to appear in RAIRO).
[3] , and , Alternating Cycles Through Given Vertices in Edge-Colored Complete Graphs, to appear in JCCCM (1994). | MR 1301222 | Zbl 0813.05042
[4] , and , Edge-Colored Complete Graphs Containing Alternating Hamiltonian Cycles, submitted.
[5] and , On Simple Hamiltonian Cycles in a 2-Colored Complete Graph, Ars Combinatoria 32(1991) 13-16. | MR 1148908 | Zbl 0751.05056
[6] and , Alternating Hamiltonian Cycles, Israel J. Mathematics 23 (1976) 126-130. | MR 411999 | Zbl 0325.05114
[7] and , Structural balance: A generalisation of Heider's theory, Psychological Review 63 (1956) 277-293.
[8] and , Graphs With Hamiltonian Cycles Having Adjacent Lines of Different Colors, J. Combinatorial Theory (B) 21 (1976) 135-139. | MR 422070 | Zbl 0287.05106
[9] , Théorie des Graphes et Structures Sociales, Gauthier-Villars, Paris (1965). | MR 221966 | Zbl 0169.26603
[10] , and , The Directed Subgraph Homeomorphism Problem, Theor. Comput. Science 10 (1980) 111-121. | MR 551599 | Zbl 0419.05028
[11] and , Alternating Cycles in Edge-Partitioned Graphs, J. Combinatorial Theory (B) 34 (1983) 77-81. | MR 701173 | Zbl 0491.05039
[12] Vertex Coverings by Monochromatic Paths and Cycles, J. of Graph Theory 7 (1983) 131-135. | MR 693029 | Zbl 0511.05046
[13] , Attitudes and Cognitive Organization, Journal of Psychology 21 (1946) 107-112.
[14] , and , Packing Problems in Edge-Colored Complete Graphs, Discrete Applied Mathematics 52(1994) 295-306. | MR 1287979 | Zbl 0806.05054
[15] , Alternating Paths in Edge-colored Complete Graphs, to appear in Discrete Applied Mathematics (1994). | MR 1318749 | Zbl 0819.05039
[16] , and , Cycles of Given Color Patterns, to appear in J. of Graph Theory (1995). | MR 1368740 | Zbl 0839.05056
[17] and , A Derivation of a Measure of Relative Balance for Social Structures and a Caracterization of Extensive Ratio Systems, Journal of Mathematical Psychology 9 (1972) 66-91. | MR 293041 | Zbl 0233.92006
[18] , Sur le Circuit Hamiltonien Bi-colore dans les Graphes Orientés, Periodica Math. Hungar. 3 (1973) 289-297. | MR 366739 | Zbl 0267.05114
[19] , Graph Theory and its Applications to Problems of Society, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM Philadelphia, 1978. | MR 508050 | Zbl 0452.05001
[20] , Alternating Cycles in Edge-Colored Graphs, J. of Graph Theory 13 (1989) 387-391. | MR 1010574 | Zbl 0679.05046