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.