UVictoria Discrete Math Seminar: Christopher Duffy

In defining colouring of oriented graphs via homomorphism one finds an easily checkable necessary condition for a valid colouring — vertices at directed distance at most two must receive different colours. With this idea in mind we extend the definition of quasi-transitive digraph to mixed graphs. In this talk we explore a full characterisation of quasi-transitive mixed graphs of degree at most three and find that the general problem of deciding if a graph admits a mixed orientation as a quasi-transitive mixed graph is NP-complete.