CanaDAM 2013 Université Memorial de Terre-Neuve, 10 - 13 juin 2013 www.smc.math.ca//2013f

Discrete Math Coast to Coast: The Maritimes and the Middle
PrÃ©sident: Chris Duffy (University of Victoria)
Org: Gary MacGillivray (University of Victoria)
[PDF]

Oriented Injective Colouring  [PDF]

We define an \textit{oriented injective $k$-colouring} of an oriented graph $G$ to be an oriented colouring such that, for all $v \in V(G)$, no two in-neighbours of $v$ are assigned the same colour, nor are any two out-neighbours. The \textit{oriented injective chromatic number} $\chi_i(G)$ is the smallest $k$ for which such a $k$-colouring of $G$ exists, i.e.~the smallest number of vertices in an oriented graph $H$ for which there is an injective homomorphism of $G$ to $H$. We consider this parameter in terms of obstructions, critical graphs, cliques, products and bounds. Joint work with R. Campbell and G. MacGillivray.

CHRIS DUFFY, University of Victoria
Game Show Scheduling and Orderings of Elements of a Product  [PDF]

Here we discuss a scheduling problem that has its root in scheduling actors. In particular we are interested in enumerating elements of the product of sets such that individual elements do not appear too frequently in the listing of the elements of the product. This problem (eventually) reduces to finding an appropriate Hamilton path in a appropriately defined graph. We show bounds for some basic parameters of the problem and describe conditions for the existence of such a path.

SHANNON FITZPATRICK, University of Prince Edward Island
Grundy Number and the Strong Product  [PDF]

A proper colouring is referred to as a Grundy colouring if every vertex has a neighbour from each of the colour classes lower than its own. The Grundy number of a graph is the maximum number of colours that can appear in such a colouring. In this talk, I will discuss bounds on the Grundy number of strong products of graphs, and classes of graph for which these bounds are exact. I will also discuss a bound on the Grundy number of the strong product of n paths of length 2, which generalizes for the strong product of n stars.

MARGARET-ELLEN MESSINGER, Mount Allison University
The Cop Number and Tree Decompositions  [PDF] [SLIDES]

We give a new bound on the cop number in terms of the treewidth of a graph. For some families of graphs, it is an improvement upon the bound of Joret, Kaminski, and Theis. However, our results give a new approach to bounding the cop number by exploiting properties of tree decompositions.

*joint work with A. Bonato, N.E. Clarke, S. Finbow, and S. Fitzpatrick

A strong edge-coloring of a graph $G$ is an edge-coloring where any two vertices belonging to distinct edges with the same color are not adjacent; the fewest colours for which a graph $G$ has a strong edge-colouring is its strong chromatic index, denoted $\chi_s'(G)$. Two major conjectures on the strong chromatic index are still oustanding -- (1) $\chi_s'(G) \leq \frac{5}{4}\Delta(G)^2$ for any graph $G$ (Erd{\H o}s and Ne\v{s}et\v{r}il, 1985) and (2) $\chi_s'(G) \leq \Delta(G)^2$ for any bipartite graph $G$ (Faudree, Gy\'arf\'as, Schelp, Tuza, 1989). In this talk, I will survey the progress that has been made on these conjectures.