Colouring complete multipartite and Kneser-type digraphs

Source abstract

The dichromatic number of a digraph $D$ is the smallest $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs, and the dichromatic number of an undirected graph is the maximum dichromatic number over all its orientations. We present bounds for the dichromatic number of Kneser graphs and Borsuk graphs, and for the list dichromatic number of certain classes of Kneser graphs and complete multipartite graphs. The bounds presented are sharp up to a constant factor. Additionally, we give a directed analogue of Sabidussi's theorem on the chromatic number of graph products.