Paths through fixed vertices in edge-colored graphs
Mathématiques informatique et sciences humaines, Tome 127 (1994), pp. 49-58.

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 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/item/MSH_1994__127__49_0/

[1] M. Bánkfalvi and Z. Bánkfalvi, Alternating Hamiltonian Circuits in 2-colored Complete Graphs, Theory of Graphs, Akadémiai Kiadô, Budapest (1968) 11-18. | Zbl

[2] A. Benkouar, Y. Manoussakis, V. Paschos and R. Saad, 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] A. Benkouar, Y. Manoussakis and R. Saad, Alternating Cycles Through Given Vertices in Edge-Colored Complete Graphs, to appear in JCCCM (1994). | MR | Zbl

[4] A. Benkouar, Y. Manoussakis and R. Saad, Edge-Colored Complete Graphs Containing Alternating Hamiltonian Cycles, submitted.

[5] A. Bialostocki and P. Dierker, On Simple Hamiltonian Cycles in a 2-Colored Complete Graph, Ars Combinatoria 32(1991) 13-16. | MR | Zbl

[6] B. Bollobàs and P. Erdös, Alternating Hamiltonian Cycles, Israel J. Mathematics 23 (1976) 126-130. | MR | Zbl

[7] D. Cartwright and F. Harary, Structural balance: A generalisation of Heider's theory, Psychological Review 63 (1956) 277-293.

[8] C.C. Chen and D.E. Daykin, Graphs With Hamiltonian Cycles Having Adjacent Lines of Different Colors, J. Combinatorial Theory (B) 21 (1976) 135-139. | MR | Zbl

[9] C. Flament, Théorie des Graphes et Structures Sociales, Gauthier-Villars, Paris (1965). | MR | Zbl

[10] S. Fortune, J. Hopcroft and J. Wyllie, The Directed Subgraph Homeomorphism Problem, Theor. Comput. Science 10 (1980) 111-121. | MR | Zbl

[11] J.W. Grossman and R. Häggkvist, Alternating Cycles in Edge-Partitioned Graphs, J. Combinatorial Theory (B) 34 (1983) 77-81. | MR | Zbl

[12] A. Gyárfás Vertex Coverings by Monochromatic Paths and Cycles, J. of Graph Theory 7 (1983) 131-135. | MR | Zbl

[13] F. Heider, Attitudes and Cognitive Organization, Journal of Psychology 21 (1946) 107-112.

[14] P. Hell, Y. Manoussakis and Zs. Tuza, Packing Problems in Edge-Colored Complete Graphs, Discrete Applied Mathematics 52(1994) 295-306. | MR | Zbl

[15] Y. Manoussakis, Alternating Paths in Edge-colored Complete Graphs, to appear in Discrete Applied Mathematics (1994). | MR | Zbl

[16] Y. Manoussakis, M. Spyratos and Zs. Tuza, Cycles of Given Color Patterns, to appear in J. of Graph Theory (1995). | MR | Zbl

[17] R. Norman and F.R. Oberts, 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 | Zbl

[18] H. Raynaud, Sur le Circuit Hamiltonien Bi-colore dans les Graphes Orientés, Periodica Math. Hungar. 3 (1973) 289-297. | MR | Zbl

[19] F. Roberts, Graph Theory and its Applications to Problems of Society, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM Philadelphia, 1978. | MR | Zbl

[20] C. Whitehead, Alternating Cycles in Edge-Colored Graphs, J. of Graph Theory 13 (1989) 387-391. | MR | Zbl