Wednesday, January 21, 2015 3:30 pm
-
3:30 pm
EST (GMT -05:00)
Barnette's conjecture and TSP tours in Barnette Graphs
| Speaker: | Arash Haddadan |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
Barnette's
conjecture
states
that
every
3-connected,
planar,
cubic,
bipartite
graph
is
Hamiltonian.
After
45
years
Barnette's
conjecture
is
not
yet
settled.
I
will
start
with
presenting
some
classic
results
towards
proving
the
conjecture.
Although
most
efforts
in
attacking
this
problem
arise
in
the
context
of
graph
theory,
it
has
also
been
studied
in
the
context
of
TSP,
showing
that
these
graphs
accept
short
TSP
tours.
In
particular,
Correa
et
al.,
showed
that
Barnette
graphs
accept
TSP
tours
of
size
1.28n,
where
n
is
the
number
of
vertices
in
the
graph.