Average-case complexity of backtrack search for coloring sparse random graphs

•We estimate the asymptotic complexity of coloring sparse random graphs.•For graphs Gn,p(n)Gn,p(n), where p(n)→0p(n)→0, the complexity tends to infinity.•For p(n)=d/np(n)=d/n, where d is constant, the expected complexity is exponential in n.•If p(n)→0p(n)→0 sufficiently slowly, the expected number of steps is polynomial in n.

We investigate asymptotically the expected number of steps taken by backtrack search for k  -coloring random graphs Gn,p(n)Gn,p(n) or proving non-k  -colorability, where p(n)p(n) is an arbitrary sequence tending to 0, and k is constant. Contrary to the case of constant p  , where the expected runtime is known to be O(1)O(1), we prove that here the expected runtime tends to infinity. We establish how the asymptotic behavior of the expected number of steps depends on the sequence p(n)p(n). In particular, for p(n)=d/np(n)=d/n, where d   is a constant, the runtime is always exponential, but it can be also polynomial if p(n)p(n) decreases sufficiently slowly, e.g. for p(n)=1/lnn.