{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:52:42Z","timestamp":1753894362362,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"Graph Theory","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Homomorphically full graphs are those for which every homomorphic image is\nisomorphic to a subgraph. We extend the definition of homomorphically full to\noriented graphs in two different ways. For the first of these, we show that\nhomomorphically full oriented graphs arise as quasi-transitive orientations of\nhomomorphically full graphs. This in turn yields an efficient recognition and\nconstruction algorithms for these homomorphically full oriented graphs. For the\nsecond one, we show that the related recognition problem is GI-hard, and that\nthe problem of deciding if a graph admits a homomorphically full orientation is\nNP-complete. In doing so we show the problem of deciding if two given oriented\ncliques are isomorphic is GI-complete.<\/jats:p>","DOI":"10.46298\/dmtcs.9957","type":"journal-article","created":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T09:35:13Z","timestamp":1696239313000},"source":"Crossref","is-referenced-by-count":0,"title":["Homomorphically Full Oriented Graphs"],"prefix":"10.46298","volume":"vol. 25:2","author":[{"given":"Thomas","family":"Bellitto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Duffy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gary","family":"MacGillivray","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2023,10,2]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/dmtcs.episciences.org\/12269\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dmtcs.episciences.org\/12269\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T09:35:14Z","timestamp":1696239314000},"score":1,"resource":{"primary":{"URL":"http:\/\/dmtcs.episciences.org\/9957"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,2]]},"references-count":0,"journal-issue":{"issue":"Graph Theory","published-online":{"date-parts":[[2023,10,2]]}},"URL":"https:\/\/doi.org\/10.46298\/dmtcs.9957","relation":{"has-preprint":[{"id-type":"arxiv","id":"2208.10727v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2208.10727v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2208.10727","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2208.10727","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"type":"electronic","value":"1365-8050"}],"subject":[],"published":{"date-parts":[[2023,10,2]]},"article-number":"9957"}}