Edge-coloured graph homomorphisms, paths, and duality

arXiv2208.12326MaRDI QIDQ6408841FDOQ6408841

Authors: Kyle Booker, Richard C. Brewster 

Publication date: 25 August 2022

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

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)

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)