Edge-coloured graph homomorphisms, paths, and duality

MaRDI QIDQ6408841arXivFDO

Authors Kyle Booker, Richard C. Brewster

Publication date 25 August 2022

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15)

Abstract: We present a edge-coloured analogue of the duality theorem for transitive tournaments and directed paths. Given a edge-coloured path $P$ whose edges alternate blue and red, we construct a edge-coloured graph $D$ so that for any edge-coloured graph $G$ ${\displaystyle }$ P o G Leftrightarrow G ot o D. ${\displaystyle }$ The duals are simple to construct, in particular $|V(D)|=|V(P)|-1$.

This page was built for publication: Edge-coloured graph homomorphisms, paths, and duality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408841)