Obstructions to some injective oriented colourings
Abstract
Each of several possible definitions of local injectivity for a homomorphism of an oriented graph $G$ to an oriented graph $H$ leads to an injective oriented colouring problem. For each case in which such a problem is solvable in polynomial time, we identify a set $\mathcal{F}$ of oriented graphs such that an oriented graph $G$ has an injective oriented colouring with the given number of colours if and only if there is no $F \in \mathcal{F}$ for which there is a locally-injective homomorphism of $F$ to $G$.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Topology and Set Theory
Advanced Graph Theory Research
Publication details
- Journal / source
- Theory and Applications of Graphs
- Publisher
- Georgia Southern University
- Publication date
- 11 June 2026
- Language
- EN