## February 20, Winter 2009: Theory Seminar

### 1:00pm in 253 ICS

# Asymptotically Optimal Frugal Colouring

## by Michael Molloy and Bruce Reed

##
Appeared in SODA 2009

## Presented by Kevin Wortman, UC Irvine

We prove that every graph with maximum degree Delta can be properly (Delta +
1)-coloured so that no colour appears more than O(log Delta/ log log Delta)
times in the neighbourhood of any vertex. This is best possible up to
the constant factor in the O(-) term. We also provide an efficient
algorithm to produce such a colouring.