On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets

DOI10.46298/dmtcs.6773zbMath1462.05136arXiv2004.08732OpenAlexW3146542902MaRDI QIDQ4987273

Christopher Duffy, Sonja Linghui Shan

Publication date: 3 May 2021

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.08732

zbMATH Keywords

complexitygraph colouringoriented graph2-edge-coloured graph

Mathematics Subject Classification ID

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

Cites Work

• Homomorphisms and colourings of oriented graphs: an updated survey
• An oriented coloring of planar graphs with girth at least five
• Homomorphisms of edge-colored graphs and Coxeter groups
• Good and semi-strong colorings of oriented planar graphs
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• On universal graphs for planar oriented graphs of a given girth
• Colored homomorphisms of colored mixed graphs
• Chromatic polynomials of oriented graphs
• An oriented 7-colouring of planar graphs with girth at least 7
• On Chromatic Number of Colored Mixed Graphs
• Oriented 5-coloring of sparse plane graphs
• Acyclic and oriented chromatic numbers of graphs
• Monotone monadic SNP and constraint satisfaction
• The complexity of satisfiability problems
• Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs
• Acyclic colorings of planar graphs

This page was built for publication: On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets