%0 Journal Article
%T Complexity of Injective Homomorphisms to Small Tournaments, and of Injective Oriented Colourings
%A Russell J. Campbell
%A Nancy E. Clarke
%A Gary MacGillivray
%J Open Journal of Discrete Mathematics
%P 1-15
%@ 2161-7643
%D 2023
%I Scientific Research Publishing
%R 10.4236/ojdm.2023.131001
%X Several<span> </span>possible<span> </span>definitions<span> </span>of<span> </span>local<span> </span>injectivity<span> </span>for<span> </span>a<span> </span>homomorphism<span> </span>of<span> </span>an<span> </span>oriented<span> </span>graph<span> </span><i>G</i><span> </span>to<span> </span>an<span> </span>oriented<span> </span>graph<span> </span><i>H</i><span> </span>are<span> </span>considered.<span> </span>In<span> </span>each<span> </span>case,<span> </span>we<span> </span>determine<span> </span>the<span> </span>complexity<span> </span>of<span> </span>deciding<span> </span>whether<span> </span>there<span> </span>exists<span> </span>such<span> </span>a<span> </span>homomorphism<span> </span>when<span> </span><i>G</i><span> </span>is<span> </span>given<span> </span>and<span> </span><i>H</i><span> </span>is<span> </span>a<span> </span>fixed<span> </span>tournament<span> </span>on<span> </span>three<span> </span>or<span> </span>fewer<span> </span>vertices.<span> </span>Each<span> </span>possible<span> </span>definition<span> </span>leads<span> </span>to<span> </span>a<span> </span>locally-injective<span> </span>oriented<span> </span>colouring<span> </span>problem.<span> </span>A<span> </span>dichotomy<span> </span>theorem<span> </span>is<span> </span>proved<span> </span>in<span> </span>each<span> </span>case.
%K Injective Graph Homomorphism
%K Oriented Colouring
%K Complexity
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=121086