Edge-coloured graph homomorphisms, paths, and duality

MaRDI QIDQ6408841arXivFDO

Authors Kyle Booker, Richard C. Brewster

Publication date 25 August 2022

Published in arXiv

Mathematics Subject Classification ID

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

arXiv classification

cs.DMmath.CO

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)