{"id":"arxiv/2607.26592","url":"https://arxiv.org/abs/2607.26592","tags":["cs.DS","cs.CC","math.CO"],"score":0,"title":"Graph k-Coloring in Average Sublinear Time","domain":"cs.DS","source":"arxiv","authors":["Cassandra Marcussen","Edward Pyne","Ronitt Rubinfeld","Asaf Shapira","Shlomo Tauber"],"reviews":0,"subject":"cs.DS","summary":"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 $Θ(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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-29","reactions":{}}