From 3-colorings to 3-flows
Speaker: | Dan Younger |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
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.