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

m a t h c a l 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 i n m a t h c a l F

for which there is a locally-injective homomorphism of

F

to

G

.

This page was built for publication: Obstructions to some injective oriented colourings