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://archive.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://archive.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://archive.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://archive.numdam.org/item/MSH_1994__127__49_0/
[1] Alternating Hamiltonian Circuits in 2-colored Complete Graphs, Theory of Graphs, Akadémiai Kiadô, Budapest (1968) 11-18. | Zbl
and ,[2] 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).
, , and ,[3] Alternating Cycles Through Given Vertices in Edge-Colored Complete Graphs, to appear in JCCCM (1994). | MR | Zbl
, and ,[4] Edge-Colored Complete Graphs Containing Alternating Hamiltonian Cycles, submitted.
, and ,[5] On Simple Hamiltonian Cycles in a 2-Colored Complete Graph, Ars Combinatoria 32(1991) 13-16. | MR | Zbl
and ,[6] Alternating Hamiltonian Cycles, Israel J. Mathematics 23 (1976) 126-130. | MR | Zbl
and ,[7] Structural balance: A generalisation of Heider's theory, Psychological Review 63 (1956) 277-293.
and ,[8] Graphs With Hamiltonian Cycles Having Adjacent Lines of Different Colors, J. Combinatorial Theory (B) 21 (1976) 135-139. | MR | Zbl
and ,[9] Théorie des Graphes et Structures Sociales, Gauthier-Villars, Paris (1965). | MR | Zbl
,[10] The Directed Subgraph Homeomorphism Problem, Theor. Comput. Science 10 (1980) 111-121. | MR | Zbl
, and ,[11] Alternating Cycles in Edge-Partitioned Graphs, J. Combinatorial Theory (B) 34 (1983) 77-81. | MR | Zbl
and ,[12] Vertex Coverings by Monochromatic Paths and Cycles, J. of Graph Theory 7 (1983) 131-135. | MR | Zbl
[13] Attitudes and Cognitive Organization, Journal of Psychology 21 (1946) 107-112.
,[14] Packing Problems in Edge-Colored Complete Graphs, Discrete Applied Mathematics 52(1994) 295-306. | MR | Zbl
, and ,[15] Alternating Paths in Edge-colored Complete Graphs, to appear in Discrete Applied Mathematics (1994). | MR | Zbl
,[16] Cycles of Given Color Patterns, to appear in J. of Graph Theory (1995). | MR | Zbl
, and ,[17] 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
and ,[18] Sur le Circuit Hamiltonien Bi-colore dans les Graphes Orientés, Periodica Math. Hungar. 3 (1973) 289-297. | MR | Zbl
,[19] Graph Theory and its Applications to Problems of Society, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM Philadelphia, 1978. | MR | Zbl
,[20] Alternating Cycles in Edge-Colored Graphs, J. of Graph Theory 13 (1989) 387-391. | MR | Zbl
,