CanaDAM 2011 University of Victoria, May 31 - June 3, 2011 www.cms.math.ca//2011

Graph Theory: Colouring
[PDF]

ARARAT HARUTYUNYAN, Simon Fraser University
Gallai's Theorem for List Coloring of Digraphs  [PDF]

A classical theorem of Gallai states that in every $k$-critical graph, the vertices of degree $k-1$ induce a graph whose blocks are either complete graphs or cycles of odd length. We provide a generalization to colorings and list colorings of digraphs, where some new phenomena arise. In particular, the problem of list coloring digraphs with the lists at each vertex $v$ having $\min\{d^{+}(v),d^{-}(v)\}$ is NP-hard. This is joint work with Bojan Mohar.

MARK KAYLL, University of Montana
Uniquely $D$-colourable digraphs with large girth  [PDF]

In a seminal 1959 \emph{Canadian J. Mathematics\/} article, Erd\H{o}s proved the existence of graphs with arbitrarily large girth and chromatic number. In 1976, Bollob\'{a}s and Sauer extended Erd\H{o}s' theorem by making the optimal colouring enjoy `uniqueness'. In 1996, Zhu generalized these results by viewing them as assertions about homomorphisms into $K_n$. We survey these antecedents and introduce a generalization to digraphs. New results are joint with Ararat Harutyunyan, Bojan Mohar (SFU) and Liam Rafferty (UMontana).

BERNARD LIDICKY, Charles University
List coloring and crossings  [PDF]

Joint work with Zdeněk Dvořák and Riste Škrekovski.

A graph $G$ is $k$-choosable if every vertex of $G$ can be properly colored whenever every vertex has a list of at least $k$ available colors. Thomassen gave a strikingly beautiful proof that every planar graph is 5-choosable. Thomassen's result can be easily generalized to graphs with one crossing. We further extend the result by showing that every graph with at most two crossings is 5-choosable.

KAILYN YOUNG, University of Victoria
2-dipath k-colourings  [PDF]

A \textit{2-dipath $k$-colouring} of an oriented graph $G$ is an assignment of $k$ colours $1,2,...,k$, to its vertices so that vertices joined by a directed path of length two are assigned different colours. We develop the basic theory including describing a homomorphism model and determining the complexity of deciding the existence of a 2-dipath $k$-colouring, and then show how to optimally colour multipartite tournaments.

Handling of online submissions has been provided by the CMS.