Atlantic Graph Theory Seminar: Dr. Ben Cameron (University of Guelph)

Title: Families of graphs containing only finitely many vertex-critical graphs.

In this talk, motivated by algorithmic aspects of graph colouring, we will consider the problem of classifying vertex-critical graphs in families of graphs. We will complete a dichotomy theorem for the number of k-vertex-critical H-free graphs when H is a graph of order four. Our results also reduce the remaining open problem for graphs of all orders to two families of graphs. Toward implementing the corresponding graph colouring algorithms, we then improve upon previous research to show tight upper bounds on the order and independence number of k-vertex-critical graphs in another family of graphs, allowing for exhaustive generation of these graphs for k at most 7 . Joint work with Chính Hoàng and Joe Sawada