5-critical triangle-free graphs
5-critical triangle-free graphs
-
Luke Postle, University of Waterloo
Fine Hall 224
A graph G is k-critical if G is not (k-1)-colorable but every proper subgraph of G is (k-1)-colorable. A natural question is what is asymptotically the minimum average degree in a k-critical 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 k-critical graphs have average degree at least (asymptotically) k - 2/(k-1). 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.