Wednesday, April 16, 2014 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Structure in Dense Triangle-free Graphs - Part 2
| Speaker: | Jim Geelen |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
Brandt
and
Thomassé
proved
that
every
n-vertex
triangle-free
graph
with
minimum
degree
greater
than
(1/3)n
is
4-colourable.
On
the
other
hand,
Hijnal
proved
that,
for
each
ε>0,
there
are
triangle-free
graphs
with
minimum
degree
greater
than
(1/3
-
ε)n$
that
have
arbitrarily
large
chromatic
number.
The
proof
of
Brandt
and
Thomassé’s
result
is
quite
hard,
but
there
are
a
number
of
related
results
with
very
nice
proofs
that
I
will
explain.
None
of
the
results
or
proofs
that
I
will
present
are
original.