CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Graph Theory: Colouring

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.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria