Graphs and Matroids Seminar - Ben Moore

Title: An application of graph "recolouring”

Abstract:

I will prove that for any graph G, if there is an edge e such that G-e has less than (k-1)!/2 cycles of length zero mod k, then the chromatic number of G is less or equal to k. In particular, I will show that if G has no cycles of length 0 mod 3, then G is 3-colourable. (Also possibly some results on "frozen" colourings)

This is joint work with Jae-Baek Lee (Kyungpook University), Mark Siggers ( Kyungpook University), Jonathan Noel (ETH Zurich / Warsaw depending on the time you read this abstract), Rick Brewster (Thompson Rivers University), and Sean Mcguinness (Thompson Rivers University)