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

Christopher Duffy; Sonja Linghui Shan

doi:10.46298/dmtcs.6773

Christopher Duffy ; Sonja Linghui Shan - On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets

dmtcs:6773 - Discrete Mathematics & Theoretical Computer Science, March 29, 2021, vol. 23 no. 1 - https://doi.org/10.46298/dmtcs.6773

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

Authors: Christopher Duffy ; Sonja Linghui Shan

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.

https://doi.org/10.46298/dmtcs.6773

Source: arXiv.org:2004.08732

Volume: vol. 23 no. 1

Section: Graph Theory

Published on: March 29, 2021

Accepted on: February 26, 2021

Submitted on: September 11, 2020

Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics,05C60

Licence: Attribution-Non Commercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)