Combinatorics and Optimization (CO) 749: Topics in Graph Theory
Topic for winter 2015: advanced techniques in graph colouring
Graph
colouring
is
a
storied
and
important
topic
of
study
in
graph
theory,
wherein
the
vertices
of
a
graph
are
assigned
colours
such
that
no
two
adjacent
vertices
receive
the
same
color.
From
the
Four
Color
Conjecture
in
the
1852
through
Heawood's
formula
for
colouring
graphs
on
surfaces
in
1896
to
the
proof
of
the
Four
Color
Theorem
in
1976,
the
central
and
natural
problem
of
determining
the
chromatic
properties
of
graphs
has
received
international
attention.
In
the
past
few
decades,
many
new
advancements
in
graph
colouring
have
been
made.
Old
questions
have
been
generalized
and
many
open
conjecture
proved.
This
course
will
focus
on
learning
these
new
advanced
techniques.
The
course
will
also
cover
some
of
the
many
variants
of
colouring:
list
colouring,
circular
colouring,
acyclic
colouring,
edge
colouring,
etc.
Recent
results
will
be
mentioned
and
open
problems
discussed
in
the
context
of
these
developments
and
the
techniques
that
enabled
their
proof.
Some
of
the
techniques
that
will
be
covered
include:
discharging,
the
potential
technique,
linear
isoperimetric
inequalities,
probabilistic
methods,
tashkinov
trees,
etc.
Grading
for
the
course
will
consist
of
a
few
challenging
problems
sets
and
a
presentation
and/or
project.
A
prerequisite
for
this
class
is
a
course
in
graph
theory.
A
working
knowledge
of
graph
theory
and
a
basic
exposure
to
graph
coloring
will
be
assumed.
Prerequisite:
Graph
Theory