Friday, Nov 5, 2010
3:30 pm, MC 5158

Dan Younger
University of Waterloo (adjunct, Professor emeritus)

From 3-colorings to 3-flows

Every loopless planar graph that is triangle-free has a vertex 3-colouring. This is Grötzsch's Theorem, put forward in 1958. Late in time, perhaps: we think of it now, anachronistically, as the case k = 3 of Tutte's 1954 k- Flow Conjectures: The famous general statements about planar k-vertex- colourings, k = 3, 4, 5, generalise to k-flows of a general graph, with the Petersen graph exception for k = 4. The statement for k = 3: Every graph without 1- or 3-cut has a 3-flow. None of these conjectures is settled. In 2003, Carsten Thomassen gave a proof of Grötzsch's Theorem, in its vertex-colouring statement, or rather, as a list-colouring statement, a proof that makes no appeal to the Euler Polyhedron Formula. To do this struck me as intrinsically good, and as a first step towards Tutte's vision. It was to study Carsten's paper that Bruce Richter and I started meeting together. Soon enough, we moved on to our own version. We were joined in this venture, for a time, by Cândida Nunes da Silva of the University of Campinas, who went on to include a version in her recent doctoral thesis. When we reached the stage where no evolutionary improvement to the vertex-colouring version presented itself, the door to a 3-flow proof opened.
I will present a proof of Grötzsch's Theorem in the dual, in terms of 3-flows, a proof that needs no appeal to Euler's Polyhedron Formula. The proof still requires properties of the plane. But we think it a second step toward Tutte's vision, in a case he did not at first envisage, k = 3.

This is joint work with Bruce Richter.