Proc. Symposium on the Theory of Computing (STOC) 2002, Journal version to appear in the Journal of Computer and System Sciences, special issue for STOC 2002.
The technique of using differential equations to approximate the mean path of Markov chains has proved very useful in the average-case analysis of algorithms. Here, we significantly expand the range of this technique, by showing that it can be used to handle algorithms that favor high-degree vertices. In particular, we consider the problem of 3-coloring sparse random graphs and analyze a ``smoothed'' version of the Brelaz heuristic. This allows us to prove that i) almost all graphs with average degree d, i.e. G(n,p=d/n), are 3-colorable for d <= 4.03, and that ii) a positive fraction of 4-regular graphs are 3-colorable. This improves over the previous lower bound of 3.847 for the G(n,p) 3-colorability threshold and gives the first non-trivial result on the 3-colorability of random regular graphs.