ICS Theory Group

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.