ORIENTED GRAPH COLOURING - QUESTIONS AND ANSWERS (BUT MOSTLY QUESTIONS)

Christopher Duffy, Assistant Professor at the University of Saskatchewan in the Department of Mathematics and Statistics 

(Learn more about the speaker here​)

ABSTRACT:

The simplicity in the standard definition of graph colouring belies an algebraic interpretation as a homomorphism. This interpretation can be exploited to provide a definition of graph colouring for oriented graphs that, in some sense, respects the orientations of the arcs. In this talk we’ll see how our intuition helps us and hinders us when we explore well-trodden graph colouring territory for oriented graph colouring. In particular, we’ll see how oriented versions of Brooks’ Theorem, the Four-Colour Theorem and Chromatic Polynomials give rise to unexpected results when recast in the context of oriented graphs.