On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets
- Resource Type
- article
- Authors
- Christopher Duffy; Sonja Linghui Shan
- Source
- Discrete Mathematics & Theoretical Computer Science, Vol vol. 23 no. 1, Iss Graph Theory (2021)
- Subject
- computer science - discrete mathematics
mathematics - combinatorics
05c60
Mathematics
QA1-939
- Language
- English
- ISSN
- 1365-8050
We consider non-trivial homomorphisms to reflexive oriented graphs in which some pair of adjacent vertices have the same image. Using a notion of convexity for oriented graphs, we study those oriented graphs that do not admit such homomorphisms. We fully classify those oriented graphs with tree-width $2$ that do not admit such homomorphisms and show that it is NP-complete to decide if a graph admits an orientation that does not admit such homomorphisms. We prove analogous results for $2$-edge-coloured graphs. We apply our results on oriented graphs to provide a new tool in the study of chromatic number of orientations of planar graphs -- a long-standing open problem.