Speaker: Giovanna Thron, University of Toronto

Title: An asymptotically tight bound on the adaptable
chromatic number

Abstract:

The adaptable coloring is an alternative graph coloring
definition:

Given a graph and an edge labeling, the goal is to color
the vertices so that no edge has the same color as both its endpoints.(Each edge dictates one forbidden color; the
two endpoints may be colored the same color as long as it's not the forbidden
color.)The adaptable chromatic
numberof a graph G is the minimum
number k such that _every_ edge labeling of G with k colors permits a vertex
coloring.

Hell and Zhu introduced this topic in 2008 and proved
that for a graph with maximum degree D, the adaptable chromatic number is at
most sqrt(2(2D-1)).

I will talk about my masters paper, which is joint work
with Mike Molloy.We strengthened Hell
and Zhu's bound to the asymptotically best possible bound of
(1+o(1))sqrt(D).I will discuss why this
bound is tight and go over the probabilistic proof.