*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 19th February, 3:00 in Fine Hall 224. Speaker: Luke Postle (Waterloo) Title: 5-critical triangle-free graphs 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. ----------- Next week: Ruidong Wang Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)