Almost all graphs with average degree 4 are 3-colorable

D. Achlioptas, Threshold phenomena in random graph coloring and satisfiability, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1999. D. Achlioptas, Setting two variables at a time yields a new lower bound for random 3-SAT, in: 32nd Annual ACM Symposium on Theory of Computing (Portland, OR, 2000), ACM, New York, 2000, pp. 28–37. Achlioptas, 1999, A sharp threshold for k-colorability, Random Struct. Algorithms, 14, 63, 10.1002/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7 D. Achlioptas, M. Molloy, The analysis of a list-coloring algorithm on a random graph, in: 38th Annual Symposium on Foundations of Computer Science (Miami, FL, 1997), IEEE Comput. Soc. Press, Los Alamitos, CA, 1997, pp. 204–212. Bender, 1978, The asymptotic number of labelled graphs with given degree sequences, J. Combin. Theory Ser. A, 24, 296, 10.1016/0097-3165(78)90059-6 Boettcher, 2001, Optimization with extremal dynamics, Phys. Rev. Lett., 86, 5211, 10.1103/PhysRevLett.86.5211 Bollobás, 1985 Brelaz, 1979, New methods to color the vertices of a graph, Comm. ACM, 22, 251, 10.1145/359094.359101 Chvátal, 1991, Almost all graphs with 1.44n edges are 3-colorable, Random Struct. Algorithms, 2, 11, 10.1002/rsa.3240020103 Erdős, 1960, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl., 5, 17 Kaporis, 2000, A note on the non-colorability threshold of a random graph, Electron. J. Combin., 7, R29, 10.37236/1507 R. Karp, M. Sipser, Maximum matchings in sparse random graphs, in: 22nd Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA, 1981, pp. 364–375. Knuth, 1990, Stable husbands, Random Struct. Algorithms, 1, 1, 10.1002/rsa.3240010102 Kurtz, 1970, Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Probab., 7, 49, 10.2307/3212147 Kurtz, 1981 M.G. Luby, M. Mitzenmacher, M.A. Shokrollahi, D.A. Spielman, V. Stemann, Practical loss-resilient codes, in: Proceedings of the 29th ACM Annual Symposium on the Theory of Computing, ACM, New York, 1997. Łuczak, 1991, Size and connectivity of the k-core of a random graph, Discrete Math., 91, 61, 10.1016/0012-365X(91)90162-U Mitzenmacher, 2001, Analyses of load stealing models based on families of differential equations, Theory Comput. System, 34, 77, 10.1007/s002240010010 Mitzenmacher, 1999, Studying balanced allocations with differential equations, Combin. Probab. Comput., 8, 473, 10.1017/S0963548399003946 Mode, 1971 Molloy, 1995, A critical point for random graphs with a given degree sequence, Random Struct. Algorithms, 6, 161, 10.1002/rsa.3240060204 Mulet, 2002, Coloring random graphs, Phys. Rev. Lett., 89, 268701, 10.1103/PhysRevLett.89.268701 Pittel, 1996, Sudden emergence of a giant k-core in a random graph, J. Combin. Theory Ser. B, 67, 111, 10.1006/jctb.1996.0036 N. Wormald, Some problems in the enumeration of labelled graphs, Ph.D. Thesis, Newcastle University, 1978. Wormald, 1995, Differential equations for random processes and random graphs, Ann. Appl. Probab., 5, 1217, 10.1214/aoap/1177004612