Almost all graphs with average degree 4 are 3-colorable

摘要

We analyze a randomized version of the Brelaz heuristic on sparse random graphs. We prove that almost all graphs with average degree d⩽4.03, i.e., G(n,p=d/n), are 3-colorable and that a constant fraction of all 4-regular graphs are 3-colorable.