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

Graph Colouring
PrÃ©sident: Christopher Martin van Bommel (St. Francis Xavier University)
[PDF]

Finding compatible circuits in eulerian digraphs.  [PDF] [SLIDES]

Let $G$ be an eulerian digraph with a fixed edge-coloring (not necessarily proper). A compatible circuit $T$ is an eulerian circuit of $G$ such that no consecutive edges in the circuit have the same color. We provide necessary and sufficient conditions for the existence of a compatible circuit in eulerian digraphs that do not contain vertices of outdegree three. We present partial results for digraphs with vertices of oudegree three.

AYSEL EREY, Dalhousie University
Chromatic Polynomials  [PDF] [SLIDES]

The chromatic polynomial $\pi(G,k)$ of a graph $G$ counts the number of proper $k$-colorings of the vertices of the graph. We discuss the location of the roots of chromatic polynomials in the complex plane. After giving a brief overview of the topic, the talk leads to the recent research results and open problems.

IGNACIO M PELAYO, Universitat PolitÃ¨cnica de Catalunya, Barcelona, Spain
Nordhaus-Gaddum-type results for locating domination  [PDF] [SLIDES]

A dominating set $W$ of a graph $G$ is locating-dominating if every vertex $v\not\in W$ is uniquely determined by the set of neighbors of $v$ in $W$. Locating-dominating sets of minimum cardinality are called $\lambda$-codes and its order is the location-domination number $\lambda(G)$. A Nordhaus-Gaddum-type result for the parameter $\lambda$ is a tight lower or upper bound relating $\lambda(G)$ and $\lambda(\overline{G})$. We present a number of N-G-type results for the location-domination number and other related parameters, some of them being valid for every connected graph, and the rest for certain graph families, such as trees, cactus or bipartites graphs.

HEDIYEH MASHHADI AVAZ TEHRANI, Brock University
Edge-choosability of Planar Graphs  [PDF]

According to the List Colouring Conjecture if $G$ is a simple graph, then $\chi^{'}(G)=\chi_{l}^{'}(G)$. In this talk, I discuss a relaxed version of this conjecture that every simple graph $G$ is edge-$(\Delta+1)$-choosable as by Vizing's Theorem $\Delta(G)\leq\chi^{'}(G)\leq\Delta(G)+1$. I proved the conjecture holds for planar graphs with maximum degree $\Delta(G)\neq5$ and without adjacent 4-cycles. This is an improvement to the previous result that every planar graph without intersecting 4-cycles with maximum degree $\Delta(G) \neq 5$ is edge-$(\Delta+1)$-choosable. This work is a joint project with Babak Farzad.

CHRISTOPHER MARTIN VAN BOMMEL, St. Francis Xavier University
An Extension of Parity Vertex Colourings  [PDF]

Parity vertex colourings are proper colourings such that each colour is incident with each face either zero or an odd number of times. In this talk, an extension of parity vertex colourings, proper $S_p$-vertex colourings, are introduced. A colouring of a plane graph is a proper $S_p$-vertex colouring if it is proper and for each face and each colour, the number of times the colour is incident with the face is zero or is congruent to $1 \bmod p$. We will discuss an upper bound on the proper $S_p$-vertex chromatic number for all plane graphs.