# Avi60

The festivities in honor of Avi Wigderson’s 60th birthday start tomorrow in Princeton, with a dream team of speakers. I will not be able to attend, but luckily a livestream will be available.

During the week, I will post a random selection of results of Avi’s.

Did you know that Avi’s first paper was an algorithm to color 3-colorable graphs using $O(\sqrt n)$ colors? Here is the algorithm, which has the flavor of Ramsey theory proofs.

Suppose all nodes have degree $< \sqrt n$, then we can easily color the graph with $\sqrt n$ colors. Otherwise, there is a node $v$ of degree $\geq \sqrt n$. The neighbors of $v$ induce a bipartite graph (because, in the 3-coloring that we are promised to exist, they are colored with whichever are the two colors that are different from the color of $v$), and so we can find in linear time an independent set of size $\geq \sqrt n / 2$. So we keep finding independent sets (which we assign a color to, and remove) of size $\geq \sqrt n /2$ until we get to a point where we know how to color the residual graph with $\leq \sqrt n$ colors, meaning that we can color the whole graph with $\leq 3 \sqrt n$ colors.