CanaDAM 2021
En ligne, 25 - 28 mai 2021

Graph Colouring -- surfaces, homomorphisms, and distinguishing
Org: Rick Brewster (Thompson Rivers University) et Benjamin Moore (University of Waterloo)

DEBRA BOUTIN, Hamilton College
Distinguishing Cube Families  [PDF]

A coloring of a graph with colors from $\{1,2,\ldots, d\}$ is said to be $d$-distinguishing if no nontrivial automorphism preserves the color classes. The distinguishing number of a graph is the smallest $d$ for which it has a $d$-distinguishing coloring. If a graph $G$ can be distinguished with 2 colors, we measure the \emph{cost} of distinguishing to be the minimum number of vertices that need to be colored say red over all 2-distinguishing colorings. In this talk, we'll go over definitions and a few examples before looking at distinguishing hypercubes, augmented cubes, and powers of cubes.

ARNOTT KIDNER, University of Victoria
Switchable 2-Colouring is Polynomial  [PDF]

Let $G$ be a $(m,n)$-mixed graph, $\Gamma$ be a permutation group acting on the colours of $G$, and $\pi \in \Gamma$ be a permutation. We define \emph{switching a vertex} $v$ with respect to $\pi$ as applying $\pi$ on the colour of each edge incident to $v$ and on the colour and direction of each arc incident to $v$.

Given an $(m,n)$-mixed graph $G$, we study of the question ``Is there a sequence of switchings so that the resulting $(m,n)$-mixed graph admits a homomorphism to a $2$-vertex target?"

We show that this problem is polynomial for all $\Gamma$.

BENJAMIN MOORE, University of Waterloo
A density bound for triangle free 4-critical graphs  [PDF]

I'll prove that every triangle free $4$-critical graph satisfies $e(G) \geq \frac{5v(G)+2}{3}$.

This is joint work with Evelyne Smith Roberge.

EVELYNE SMITH-ROBERGE, University of Waterloo
Local choosability of planar graphs  [PDF]

In 1994, Thomassen famously proved that every planar graph is 5-choosable. Later, he proved that every planar graph of girth at least five is 3-choosable. In this talk, I will introduce the concept of a local girth list assignment: a list assignment wherein the list size of each vertex depends not on the girth of the graph, but only on the length of the shortest cycle in which the vertex itself is contained. I will present a local choosability theorem for planar graphs, unifying the two theorems of Thomassen mentioned above. (Joint work with Luke Postle.)

ZHOUNINGXIN WANG, IRIF, Universite de Paris
Circular chromatic number of signed graphs  [PDF]

A circular $r$-coloring of a signed graph $(G, \sigma)$ is an assignment $\varphi$ of points of a circle of circumference $r$ to vertices of $G$ such that for positive edge $uv$, $\varphi(u)$ and $\varphi(v)$ have distance at least $1$, and for negative edge $uv$, $\varphi(v)$ and the antipodal of $\varphi(u)$ have distance at least $1$. The circular chromatic number of $(G, \sigma)$ is $\chi_c(G, \sigma)=\inf\{r\mid \text{$(G, \sigma)$ admits a circular $r$-coloring}\}.$ We bound the circular chromatic number of several classes: signed $k$-chromatic graphs, signed $d$-degenerate graphs and signed planar graphs. This is joint work with Reza Naserasr and Xuding Zhu.