Graph k-Coloring in Average Sublinear Time

Abstract

Graph $k$-coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a $k$-coloring over the set of all $k$-colorable graphs on $n$ vertices. A highly influential result of Dyer-Frieze from 1989 gave an algorithm with $O(n^2)$ average runtime for constant $k$. This quadratic runtime appeared natural (and possibly even optimal) since almost all $k$-colorable graphs have $\hat{I}˜(n^2)$ edges, so one needs at least this time in order to read the (entire) input. However, this was later improved by Kučera in 1995 to average runtime $O(n^2/k)$ for every $k\le n^c$ where $c\in (0,1)$. Nevertheless, in the most interesting case of $k=O(1)$, the best-known bound remained quadratic in $n$. The true average complexity of the $k$-coloring problem has remained elusive for the last three decades. We break the longstanding quadratic barrier. Our main result in this paper shows that the exact average-case complexity of this fundamental problem is $\hat{I}˜(nk)$ for every $k\le n^{c^{\prime }}$ and some $c^{\prime }\in (0,1)$. For $k=O(1)$, this reveals the average sublinear nature of $k$-colorability: the average-case complexity is linear in $n$, and thus sublinear in the size of the input. We further show that our $\hat{I}˜(nk)$ average runtime is optimal, since a simple bound proves that every algorithm that correctly $k$-colors all $k$-colorable graphs requires $\hat{I}\text{c◯}(nk)$ average runtime. Our proofs draw on ideas from sublinear and local algorithms and also yield a local computation algorithm (LCA) for $k$-coloring with average-case probe complexity $\text{poly}(k)$. A key new ingredient in our algorithm is a method for certifying the unique colorability of random subgraphs, using tools from the theory of graph regularity.

40 pages, 5 figures. FOCS 2026

Topics & keywords