CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Graph coloring II
Président: Ingo Schiermeyer (Technische Universität Bergakademie Freiberg)

MARK KAYLL, University of Montana
On uniquely $G$-colourable digraphs of large girth  [PDF]

In 1959, P\'{a}l Erd\H{o}s published an article establishing the existence of graphs with arbitrarily large girth and arbitrarily high chromatic number. This seminal paper not only exposed a facet of a diamond---the then-nascent probabilistic method---but also sparked a cottage industry refining and polishing his gem. Partly historical, partly contemporary, this talk traces a thread generalizing colouring to `homomorphing' and analogizing graphs to digraphs.

AMIRHOSSEIN KAZEMINIA, Simon Fraser University
Counting homomorphisms modulo prime  [PDF]

A wide range of graph problems can be encoded as questions about the existence or the number of homomorphisms between graphs. The problem of exact counting of graph homomorphisms has been extensively studied. We study the complexity of the related problem of counting homomorphisms from an input graph to a fixed graph $H$ modulo a prime number $p$. The properties of modular counting may be very different from those of exact counting. However, it was shown that in many cases the two problems have the same complexity. These include counting homomorphisms to square-free graphs modulo $2$, and counting homomorphisms to trees modulo an arbitrary prime $p$. In this talk, we improve upon the previous results by significantly simplifying the existing proofs and classifying the complexity of counting homomorphisms to square-free graphs $H$ modulo an arbitrary prime $p$ provided $H$ has a vertex whose degree is not 1 modulo $p$.

ELHAM ROSHANBIN, Alzahra University
Star edge colouring of graphs  [PDF]

A star edge (vertex) colouring of a graph is a proper colouring of its edges (vertices) in which there is no bi-coloured path or cycle (path) of length (order) four. It is known that its vertex version has application in optimization problems. Recently its edge version has received a lot of attention. The minimum number of colours that is needed for the star edge colouring of a graph, is called its star chromatic index. It is known that finding the star chromatic index is NP-hard. Although there is a tight bound on the star chromatic index of trees in terms of their maximum degree, finding the star chromatic index even for trees is not trivial. In this talk we state some of the known results and open problems on the star chromatic index of graphs, and we present some polynomial time algorithms for computing the star chromatic index of trees.

NATHAN SINGER, Simon Fraser University
Colouring Complexes  [PDF]

Given a 3-colourable graph $H$, the colouring complex $B(H)$ is the graph which has all the independent sets which are colour classes of $H$ as its vertices and two vertices $u,v \in V(B(H))$ joined by an edge if the colour classes $u$ and $v$ appear together in a 3-colouring of $H$. The graph $B(H)$ is 3-colourable. Graphs for which $B(B(H))$ is isomorphic to $H$ are termed reflexive graphs. We show that the line graph $H = L(G)$ of an outerplanar graph $G$ which is cubic (after including half-edges at vertices whose degree was originally less than 3) is reflexive if and only if $G$ is triangle-free. We then discuss other classes of reflexive graphs. This is joint work with Fiachra Knox and Bojan Mohar.

FEIRAN(FRANK) YANG, University of Victoria
2-limited broadcast domination on subcubic graph  [PDF]

For a graph $G$, a function $f: V(G) \rightarrow \{0,1,2...,diam(G)\}$ is called a broadcast on $G$. For each vertex $u \in V(G)$, if there exists a vertex $v$ in $G$ such that $f(v) > 0$ and $d(u,v) \le f(v)$, then $f$ is called a dominating broadcast on $G$. In this talk, we consider a limited version of the broadcast, where $f: V(G) \rightarrow \{0,1,2\}$. We will prove that the 2-limited broadcast domination number of a $(C_4,C_6)$-free cubic graph is at most a third of the its order. For this purpose, we prove a stronger result on $(C_4,C_6)$-free subcubic graph. This is joint work with Mike Henning and Gary MacGillivray.