Paths through fixed vertices in edge-colored graphs. (English) Zbl 0826.68064

This paper considers a graph \(G\) with its edges coloured, not necessarily properly, in \(k\) colours. Given a subset \(S\subseteq V(G)\), it is shown that the problem of finding a path \(P\) through \(S\) such that no pair of consecutive edges in \(P\) have the same colour is NP-complete when \(k=2\).
In the case of \(G\) a complete graph with a 2-edge-colouring, a polynomial characterization is given.
An investigation of \((s,t)\) paths is also included. (An \((s,t)\) path is a path of length \(s+t\) in which there are \(s\) consecutive edges of one colour and \(t\) consecutive edges of a different colour).


68Q25 Analysis of algorithms and problem complexity
05C38 Paths and cycles
68R10 Graph theory (including graph drawing) in computer science
Full Text: Numdam EuDML