Online talk: Benjamin Moore

Monday, March 15, 3pm ET (7pm GMT, 8am Tue NZDT)
Benjamin Moore, University of Waterloo
A density bound for triangle free 4-critical graphs

Password: email rose.mccarty ~at~ uwaterloo ~.~ ca if you need the password


Carsten Thomassen showed that every girth 5 graph embeddable in the torus or projective plane is 3-colourable. A complementary result of Robin Thomas and Barrett Walls shows that every girth 5 graph embedded in the Klein bottle is 3-colourable.

I’ll show neither the embeddability condition nor the girth 5 condition is needed in the above theorems by showing that every triangle-free 4-critical graph has average degree slightly larger than 10/3.

This is joint work with Evelyne Smith Roberge.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.