Title: Hamilton cycles in cubic planar graphs
| Speaker: | Frantisek Kardos |
| Affiliation: | University of Bordeaux |
| Room: | MC 5479 |
Abstract: Tait
conjectured
in
1884
that
each
cubic
planar
graph
contains
a
Hamilton
cycle.
Had
the
conjecture
been
true,
it
would
have
implied
the
Four
Color
Theorem.
However,
it
was
disproved
by
Tutte
in
1946.
Later
on,
other
counterexamples
with
different
structural
properties
were
found.
On
the
other
hand,
for
several
subclasses
of
cubic
planar
graphs
Hamiltonicity
was
proven.
In
general,
the
problem
of
founding
a
Hamilton
cycle
in
a
cubic
planar
graph
turned
out
to
be
NP-complete.
All
known
counterexamples
to
Tait's
conjecture
contain
(i)
odd
cycles
and
(ii)
faces
of
large
size.
That's
why
Barnette
formulated
in
the
60s
two
conjectures
in
the
form
of
sufficient
conditions
for
the
Hamiltonicity
of
cubic
planar
graphs:
He
conjectured
that
bipartite
cubic
planar
graphs,
as
well
as
cubic
planar
graphs
with
faces
of
size
at
most
6,
are
Hamiltonian.
We
will
present
results,
methods
and
ideas
leading
to
a
computer-assisted
proof
of
the
latter.