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).
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).
Reviewer: R.E.L.Aldred (Dunedin)
MSC:
68Q25 | Analysis of algorithms and problem complexity |
05C38 | Paths and cycles |
68R10 | Graph theory (including graph drawing) in computer science |