5critical trianglefree graphs
5critical trianglefree graphs

Luke Postle, University of Waterloo
Fine Hall 224
A graph G is kcritical if G is not (k1)colorable but every proper subgraph of G is (k1)colorable. A natural question is what is asymptotically the minimum average degree in a kcritical graph. In the 60's it was conjectured that a construction of Ore gives the best possible answer. Recently, Kostochka and Yancey proved this conjecture by showing that kcritical graphs have average degree at least (asymptotically) k  2/(k1). One may wonder if the lower bound can be improved if certain subgraphs are forbidden. We prove this is true for k=5 when forbidding triangles.