### On Steinberg's Conjecture: 3-coloring certain planar graphs

- Series
- Graph Theory Seminar
- Time
- Thursday, April 14, 2011 - 12:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Peter Whalen – Math, GT

Steinberg's Conjecture states that any planar graph without cycles of
length four or five is three colorable. Borodin, Glebov, Montassier,
and Raspaud showed that planar graphs without cycles of length four,
five, or seven are three colorable and Borodin and Glebov showed that
planar graphs without five cycles or triangles at distance at most two
apart are three colorable. We prove a statement similar to both of
these results: that any planar graph with no cycles of length four
through six or cycles of length seven with incident triangles distance
exactly two apart are three colorable. Special thanks to Robin Thomas
for substantial contributions in the development of the proof.