Homomorphically Full Oriented Graphs

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 orientat...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2023-01, Vol.25:2 (Graph Theory), p.1-14
Main Authors: Bellitto, Thomas, Duffy, Christopher, MacGillivray, Gary
Format: Article
Language:English
Subjects:
05c60, 05c20, 68q17
Algorithms
computer science - discrete mathematics
Graph theory
Graphs
mathematics - combinatorics
Recognition
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1365-8050
1365-8050
DOI:10.46298/dmtcs.9957