Our results imply the existence of simple polynomial-time certifying algorithms to decide the $k$-colourability of (co-gem, $H$)-free graphs for all $k$ and all $H$ of order $4$ by searching for the vertex-critical graphs as induced subgraphs. As time allows, we will sketch some of the new ideas used in our proofs, including an application of Sperner's Theorem on the number of antichains in a partially ordered set.

A $k$-colouring is called frozen if there is no vertex whose colour can be changed so that the result is still a $k$-colouring. A frozen colouring corresponds to an isolated vertex of the reconfiguration graph. Equivalently, a frozen $k$-colouring is a partition of the vertices into at most $k$ sets, each of which is both independent and dominating. The terms fall colouring and indominable have also been used. We have found several new classes of graphs with frozen colourings and an operation which transforms a $k$-chromatic graph with a frozen $(k+1)$-colouring into a $(k+1)$-chromatic graph with a frozen $(k+2)$-colouring, without using the “join” operation or adding universal vertices. I will discuss the recently resolved problem: For which values of $k$ and $t$ does there exist a $k$-colourable graph with no induced path on $t$ vertices with a frozen $(k+1)$-colouring?

This is joint work with Manoj Belavadi and Elias Hildred.

In this talk we consider the full $H$-colouring problem when $H$ is a tree; in particular, we are interested in the optimal time for recognizing a fully $H$-colourable graph. We present a linear time algorithm to solve the full $H$-colouring problem when $H$ is a path. We also define the class of fully tree-colourable graphs as the family of graphs admitting a full homomorphism to some tree, and exhibit a characterization in terms of minimal induced subgraphs for such a class.

Our research was focused on determining explicit formulas and polynomial time algorithms for the broadcast independence number of various types of graphs. This parameter is difficult to compute for graphs in general, so we restrict the problem to specific classes of graphs to make use of their special structural properties to solve the problem. For a graph from a given class, we constructed a new graph, called the broadcast ball intersection graph. We were able to show that if the broadcast ball intersection graph is weakly chordal, then broadcast independence is polynomial time solvable for the given class of graphs. This talk is based on joint work with Richard Brewster (TRU) and Jing Huang (UVic).

Our theorem generalizes the more technical version of the Lovasz, Thomassen, Wu, Zhang theorem.

This is joint work with Soffia Arnadottir, Evelyne Smith Roberge, Zdenek Dvorak, Bernard Lidicky, and Robert Samal.

We call a complete signed graph positive (negative) if every edge is positive (negative). We study the following Ramsey problem on signed graphs -- for positive integers $s$ and $t$, what is the smallest $n$ such that every signed complete graph on $n$ vertices has an equivalent signed complete graph containing either a negative $K_s$ or positive $K_t$. This "signed Ramsey number" is denoted $r_{\pm}(s,t)$. We show how a variety of approaches lead to upper and lower bounds on $r_{\pm}(s,t)$, settle an open problem by establishing the exact value of $r_{\pm}(4,t)$ for every $t$, and determine the asymptotics of $r_{\pm}(5,t)$ and $r_{\pm}(6,t)$.