# Approximate Colouring using Semi Definite Programming

Speaker:

## Time:

Monday, 14 November 2011, 16:00 to 17:00

## Venue:

• A-212 (STCS Seminar Room)

Determining the chromatic number of a graph is known to be NP-hard. We will consider the problem of coloring a $k$-colorable graph on n vertices with $n^{\alpha}$ colors (where $\alpha < 1$). We will give an algorithm for this problem using Semi Definite Programming (a generalization of LP ).