DMS Combinatorics Seminar

Speaker: Jessica McDonald (Auburn University)

Title: Strong Colouring with $K_3$'s and $K_4$'s

Abstract: If $H$ is a graph, and $G$ is obtained from $H$ by gluing on vertex-disjoint copies of $K_t$, then when can we guarantee that $G$ is $t$-colourable? The Strong Colouring Conjecture posits that $\chi(G)\leq t$ whenever $t\geq 2\Delta(H)$. We'll discuss this seemingly very difficult conjecture, with particular focus on the elusive case of $\Delta(H)=2$. We'll describe new joint work with Dalal and Shan where the "cycles plus $K_4$'s" problem is reduced to a problem about "strong colouring" with $K_3$'s.