Wednesday, April 2, 2014 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Structure in Dense Triangle-free Graphs Part 1
Speaker: | Jim Geelen |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
Brandt
and
Thomass\’
e
proved
that
every
$n$-vertex
triangle-free
graph
with
minimum
degree
greater
than
$\frac
1
3
n$
is
$4$-colourable.
On
the
other
hand,
Hijnal
proved
that,
for
each
$\epsilon>0$,
there
are
triangle-free
graphs
with
minimum
degree
greater
than
$(\frac
1
3
-
\epsilon)n$
that
have
arbitrarily
large
chromatic
number.
The
proof
of
Brandt
and
Thomass\’
e’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.