Homomorphically Full Oriented Graphs
From MaRDI portal
Publication:6506450
DOI10.46298/DMTCS.9957arXiv2208.10727MaRDI QIDQ6506450FDOQ6506450
Authors: Thomas Bellitto, Christopher Duffy, Gary MacGillivray 
Abstract: Homomorphically full graphs are those for which every homomorphic image is isomorphic to a subgraph. We extend the definition of homomorphically full to oriented graphs in two different ways. For the first of these, we show that homomorphically full oriented graphs arise as quasi-transitive orientations of homomorphically full graphs. This in turn yields an efficient recognition and construction algorithms for these homomorphically full oriented graphs. For the second one, we show that the related recognition problem is GI-hard, and that the problem of deciding if a graph admits a homomorphically full orientation is NP-complete. In doing so we show the problem of deciding if two given oriented cliques are isomorphic is GI-complete.
Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
This page was built for publication: Homomorphically Full Oriented Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6506450)
