# zbMATH — the first resource for mathematics

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).

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