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.