Edge-coloured graph homomorphisms, paths, and duality

Abstract

We present a 2-edge-coloured analogue of the duality theorem for transitive tournaments and directed paths. Given a 2-edge-coloured path \( P \) whose edges alternate blue and red, we construct a 2-edge-coloured graph \( D \) so that for any 2-edge-coloured graph \( G \),

\[
P \to G \iff G \not\to D.
\]

The duals are simple to construct, in particular \(|V(D)| = |V(P)| -1.\)