Recent Progress on Tutte's 3-flow Conjecture
Speaker: | Bruce Richter |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
Tutte's
3-flow
conjecture
asserts
that
every
graph
with
no
1-
or
3-edge-cut
has
an
orientation
so
that,
at
every
vertex,
the
number
of
arcs
pointing
in
is
the
same
(modulo
3)
as
the
number
of
arcs
pointing
out.
It
is
known
that
it
suffices
to
prove
that
every
5-edge-connected
graph
has
such
an
orientation.
Recently,
Thomassen
made
a
breakthrough,
proving
this
for
8-edge-connected
graphs.
There
is
now
a
very
simple
proof
that
it
holds
for
6-edge-connected
graphs.
Indeed,
this
is
proved
by
showing
that,
modulo
3,
prescribing
the
individual
out-degrees
at
every
vertex
(to
sum
to
|E(G)|
modulo
3)
is
achievable
in
6-edge-connected
graphs.
With
Thomassen
and
Younger,
we
proved
that
this
stronger
result
also
holds
for
5-edge-connected
planar
graphs.
Both
proofs
will
be
outlined
in
this
talk.