New Tools for Graph Coloring

How to color $3$ colorable graphs with few colors is a problem of longstanding interest. The best polynomial-time algorithm uses $n^{0.2130}$ colors.

We explore the possibility that more levels of Lasserre Hierarchy can give improvements over previous algorithms. While the case of general graphs is still open, we can give analyse the Lasserre relaxation for two interesting families of graphs.

For graphs with low threshold rank (a class of graphs identified in the recent paper of Arora et al. on the unique games problem), Lasserre relaxations can be used to make progress towards a coloring with $O(\log n)$ colors in $n^{O(D)}$ time, where $D$ is the threshold rank of the graph. The main idea is inspired by recent work of Barak, Raghavendra and Steurer on using Lasserre Hierarchy for unique games.

For distance transitive graphs of diameter $\Delta$, we can show how to color them using $O(\log n)$ colors in $n^{2^{O(\Delta)}}$ time. This family is interesting because the family of low-diameter graphs is easily seen to be complete for coloring with $n^{\epsilon}$ colors. The distance-transitive property just says that the graph ``looks'' the same in all neighborhoods.

I will also go over the connection between threshold rank and lasserre rounding, which is first described in BRS.