Title: Detailed structure of embedded 4-critical triangle-free graphs
| Speaker: | Zdenek Dvorak |
| Affiliation: | Charles University, Prague |
| Room: | MC 6486 |
Abstract:
By
a
well-known
theorem
of
Grotzsch,
every
triangle-free
planar
graph
is
3-colorable.
This
result
has
been
extended
in
many
ways,
especially
for
graphs
embedded
in
other
surfaces.
In
this
talk,
we
explore
the
following
question:
given
a
triangle-free
graph
G
embedded
in
the
plane
(or
another
surface)
and
a
set
S
of
vertices
of
G,
which
3-colorings
of
S
extend
to
a
3-coloring
of
G?
Algorithmically,
this
question
was
solved
by
Dvorak,
Kral
and
Thomas
(2009).
However,
we
are
more
interested
in
the
structural
aspects:
can
G
be
decomposed
into
a
bounded
number
of
well-behaved
pieces
which
determine
the
set
of
extendable
colorings
of
S?
We
present
a
positive
answer
to
this
question
which
we
obtained
in
a
joint
work
with
Bernard
Lidicky.