An improved procedure for colouring graphs of bounded local density

The chromatic number of graphs of maximum degree $\Delta$ has been studied extensively. A greedy coloring procedure shows that any graph has a proper coloring with $\Delta+1$ colors, and this is sharp, as shown by the complete graph of $\Delta+1$ vertices. However, this simple upper bound can often be improved significantly if one excludes some configurations locally or globally. For instance, it is known that triangle-free graphs have much smaller chromatic number, namely $O(\Delta/\log \Delta)$ (Johansson 1996).

Consider a vertex $v$, and count the number of edges among its (at most $\Delta$) neighbors. This number is clearly at most ${\Delta \choose 2}$, and it is $0$ if the graph is triangle-free. We say that the graph is $\sigma$-sparse if for each vertex $v$, this number of edges is at most $(1-\sigma){\Delta \choose 2}$. Molloy and Reed proved that $\sigma$-sparse graphs, for $\sigma>0$, can be colored with $(1-\epsilon)\Delta$ colors, for some $\epsilon>0$ depending only on $\sigma$, by a simple randomized procedure:

1. color all the vertices with random colors,
2. uncolor vertices which have received the same color as some of their neighbors, and
3. color the uncolored vertices deterministically (since they have a specific structure, with high probability).

This result is a crucial ingredient in a general approach consisting in dividing graphs into $\sigma$-sparse components on one side, and much denser components on the other side, that are colored using different techniques (dense components would typically be colored deterministically, or with random permutations of colors, rather than with random colors). This powerful approach, pioneered by Molloy and Reed, has been rediscovered recently in the field of distributed computing.

Moreover, $\sigma$-sparse graphs appear the context of some longstanding open problems in graph coloring. One is a fascinating conjecture of Reed, which asserts that every graph with maximum degree $\Delta$ and clique number $\omega$ admits a proper coloring with at most $\lceil (\Delta+\omega+1)/2 \rceil$ colors. Another is a classic conjecture of Erdős and Nešetřil, which states that the edges of a graph of maximum degree $\Delta$ can be colored with $1.25\Delta^2$ colors in such a way that each color class forms a matching as an induced subgraph. This latter problem can be understood in terms of the chromatic number of squares of line graphs, and such graphs turn out to be $\sigma$-sparse, for a surprising large value of $\sigma$.

The authors of the present paper obtain an improved bound on the chromatic number of $\sigma$-sparse graphs, which yields state-of-the-art progress on Reed’s conjecture and the Erdős-Nešetřil conjecture. They achieve this through the implementation and analysis of a “random priority assignment” uncoloring procedure in Step 2 above, which allows for a more efficient iteration of Steps 1 and 2 in a semirandom coloring procedure. In this way, they not only improve on previous bounds, but also obtain a bound with a leading term that is asymptotically optimal as $\sigma \to 0$.