KATHIE CAMERON, Wilfrid Laurier University
Rainbow Matchings in Bipartite Graphs  [PDF]

Given a graph whose edges are coloured, a rainbow matching is a matching whose edges have distinct colours. We give a polytime algorithm for finding a rainbow perfect matching in a complete bipartite graph where each colour is used for at most three edges. We prove that finding a rainbow perfect matching is NP-hard for 3-regular bipartite graphs where each colour is used for at most two edges. This is joint work with Ashkan Aazami.

CHRISTOPHER DUFFY, University of Victoria
The Firefighter Problem - Weights and Sets  [PDF]

The Firefighter Problem describes a discrete-time process that models the spread of a fire using the vertices of the graph. We consider algorithms and complexity results for the related problems of determining when a fixed set of vertices can be protected from burning and determining the strategy that minimizes the weight of the vertices that burn.

JESSICA ENRIGHT, University of Alberta
Set Representation Graph Games  [PDF]

Combinatorial games on graphs are an active area of study. We present several new types of games using set representations of graphs that are all generalisations of node-Kayles. We show that resolving the outcome of a position in these games is PSPACE-complete, but give algorithms for resolving restricted types of positions in polynomial time when playing these games with trees.

ELAINE ESCHEN, West Virginia University
On deciding whether the distinguishing chromatic number of a graph is at most two  [PDF]

A vertex $k$-coloring of graph $G$ is distinguishing if the only color-preserving automorphism of $G$ is the identity. The distinguishing chromatic number of $G$, ${\chi}_D(G)$, is the smallest $k$ such that $G$ admits a proper distinguishing $k$-coloring. When $k \geq 3$, deciding whether ${\chi}_D(G) \leq k$ is NP-hard. We show that when $k = 2$ this problem is at least as hard as graph automorphism but no harder than graph isomorphism. (With Hoàng, Sritharan, Stewart)

DONOVAN HARE, University of British Columbia, Okanagan Campus
A Note on the Hardness of Graph Diameter Augmentation Problems  [PDF]

The \textsc{Diameter-D Augmentation} problem takes as input a graph $G=(V,E)$ and a positive integer $k$ and asks whether there exists a set $E_2$ of at most $k$ new edges so that the graph $G_2=(V,E\cup E_2)$ has diameter $D$. This problem is NP-hard for $D \ge 2$. In this talk, we give a parameterized reduction from \textsc{Dominating Set} to \textsc{Diameter-$D$ Augmentation} to prove that \textsc{Diameter-D Augmentation} is $W[2]$-hard.

Co-authors: James Nastos and Yong Gao, UBC, Okanagan.

Handling of online submissions has been provided by the CMS.