CanaDAM 2015
University of Saskatchewan, June 1 - 4, 2015

Colourings, colour graphs, and homomorphisms
Organizer and Chair: Gary MacGillivray (University of Victoria)

STEFAN BARD, University of Victoria
Hamiltonicity of SDR graphs and colouring graphs  [PDF]

Given a collection of sets $S$, the SDR graph of $S$ is the graph whose vertices are systems of distinct representatives (SDRs) of $S$, with two SDRs adjacent if they differ in the representative of exactly one set. Given a graph $G$ and an integer $k \geq \chi(G)$, the $k$-colouring graph of $G$ is the graph whose vertices are $k$-colourings of $G$, with two colourings adjacent if they differ in the colour of exactly one vertex. We give results on Hamiltonicity and connectivity of such graphs, and relate them with an examination of colouring graphs of complete multipartite graphs.

RICHARD BREWSTER, Thompson Rivers University
The complexity of graph recoloring and reconfigurations  [PDF]

The fundamental question addressed is as follows: given a two colourings of graph, is it possible to change the first into the second by successively recolouring one vertex at a time (and maintaining a proper colouring throughout the process)? For $k$-colourings Cereceda, van den Heuvel, and Johnson proved this problem is polynomial time solvable for $k$ at most 3, whereas Bonsma and Cereceda have shown for $k$ at least 4 the problem is PSPACE-complete. We examine this topic, as well as the question of when the answer is YES for any two colourings, with a particular focus on circular $(p,q)$-colourings.

CHRISTOPHER DUFFY, University of Victoria
Dropping ``Proper" in Vertex Colourings of Mixed Graphs.  [PDF]

Graph homomorphisms to reflexive targets can be used to define vertex colourings of mixed graphs which both take into account the adjacency type between vertices and allow adjacent vertices to be assigned the same colour, provided that we require these \emph{simple colourings} use at least two different colours. We explore simple colourings of families of mixed graphs. For some families, including oriented planar graphs and $k$-edge-coloured planar graphs, the chromatic number of the mixed graph equals the minimum number of colours in a simple colouring.

GARY MACGILLIVRAY, University of Victoria
Locally-injective homomorphisms to tournaments  [PDF]

Possible definitions of local injectivity for a homomorphism of an oriented graph $G$ to an oriented graph $H$ include the following: for each vertex of $G$ the mapping is injective when restricted to (i) its closed in-neighbourhood; or (ii) its closed in-neighbourhood and closed out-neighbourhood separately; or (iii) its closed in-neighbourhood and closed out-neighbourhood together. We focus on the situation where $H$ is a reflexive tournament and describe dichotomy theorems for the complexity of the locally injective homomorphism problem in all cases. Partial results for the case where $H$ is an irreflexive tournament are also mentioned.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Saskatchewan