{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T23:26:53Z","timestamp":1783985213537,"version":"3.55.0"},"reference-count":25,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3607,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,9]]},"DOI":"10.1016\/s0022-0000(03)00120-x","type":"journal-article","created":{"date-parts":[[2003,10,9]],"date-time":"2003-10-09T00:36:33Z","timestamp":1065659793000},"page":"441-471","source":"Crossref","is-referenced-by-count":28,"title":["Almost all graphs with average degree 4 are 3-colorable"],"prefix":"10.1016","volume":"67","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(03)00120-X_BIB1","unstructured":"D. Achlioptas, Threshold phenomena in random graph coloring and satisfiability, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1999."},{"key":"10.1016\/S0022-0000(03)00120-X_BIB2","doi-asserted-by":"crossref","unstructured":"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\u201337.","DOI":"10.1145\/335305.335309"},{"issue":"1","key":"10.1016\/S0022-0000(03)00120-X_BIB3","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7","article-title":"A sharp threshold for k-colorability","volume":"14","author":"Achlioptas","year":"1999","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/S0022-0000(03)00120-X_BIB4","doi-asserted-by":"crossref","unstructured":"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\u2013212.","DOI":"10.1109\/SFCS.1997.646109"},{"key":"10.1016\/S0022-0000(03)00120-X_BIB5","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/0097-3165(78)90059-6","article-title":"The asymptotic number of labelled graphs with given degree sequences","volume":"24","author":"Bender","year":"1978","journal-title":"J. Combin. Theory Ser. A"},{"key":"10.1016\/S0022-0000(03)00120-X_BIB6","doi-asserted-by":"crossref","first-page":"5211","DOI":"10.1103\/PhysRevLett.86.5211","article-title":"Optimization with extremal dynamics","volume":"86","author":"Boettcher","year":"2001","journal-title":"Phys. Rev. Lett."},{"key":"10.1016\/S0022-0000(03)00120-X_BIB7","series-title":"Random Graphs","author":"Bollob\u00e1s","year":"1985"},{"key":"10.1016\/S0022-0000(03)00120-X_BIB8","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/359094.359101","article-title":"New methods to color the vertices of a graph","volume":"22","author":"Brelaz","year":"1979","journal-title":"Comm. ACM"},{"issue":"1","key":"10.1016\/S0022-0000(03)00120-X_BIB9","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/rsa.3240020103","article-title":"Almost all graphs with 1.44n edges are 3-colorable","volume":"2","author":"Chv\u00e1tal","year":"1991","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/S0022-0000(03)00120-X_BIB10","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"10.1016\/S0022-0000(03)00120-X_BIB11","doi-asserted-by":"crossref","first-page":"R29","DOI":"10.37236\/1507","article-title":"A note on the non-colorability threshold of a random graph","volume":"7","author":"Kaporis","year":"2000","journal-title":"Electron. J. Combin."},{"key":"10.1016\/S0022-0000(03)00120-X_BIB12","doi-asserted-by":"crossref","unstructured":"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\u2013375.","DOI":"10.1109\/SFCS.1981.21"},{"issue":"1","key":"10.1016\/S0022-0000(03)00120-X_BIB13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/rsa.3240010102","article-title":"Stable husbands","volume":"1","author":"Knuth","year":"1990","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/S0022-0000(03)00120-X_BIB14","doi-asserted-by":"crossref","first-page":"49","DOI":"10.2307\/3212147","article-title":"Solutions of ordinary differential equations as limits of pure jump Markov processes","volume":"7","author":"Kurtz","year":"1970","journal-title":"J. Appl. Probab."},{"key":"10.1016\/S0022-0000(03)00120-X_BIB15","series-title":"Approximation of Population Processes","author":"Kurtz","year":"1981"},{"key":"10.1016\/S0022-0000(03)00120-X_BIB16","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/258533.258573"},{"issue":"1","key":"10.1016\/S0022-0000(03)00120-X_BIB17","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0012-365X(91)90162-U","article-title":"Size and connectivity of the k-core of a random graph","volume":"91","author":"\u0141uczak","year":"1991","journal-title":"Discrete Math."},{"issue":"1","key":"10.1016\/S0022-0000(03)00120-X_BIB18","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s002240010010","article-title":"Analyses of load stealing models based on families of differential equations","volume":"34","author":"Mitzenmacher","year":"2001","journal-title":"Theory Comput. System"},{"issue":"5","key":"10.1016\/S0022-0000(03)00120-X_BIB19","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1017\/S0963548399003946","article-title":"Studying balanced allocations with differential equations","volume":"8","author":"Mitzenmacher","year":"1999","journal-title":"Combin. Probab. Comput."},{"key":"10.1016\/S0022-0000(03)00120-X_BIB20","series-title":"Multitype Branching Processes. Theory and Applications","author":"Mode","year":"1971"},{"issue":"2\u20133","key":"10.1016\/S0022-0000(03)00120-X_BIB21","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/rsa.3240060204","article-title":"A critical point for random graphs with a given degree sequence","volume":"6","author":"Molloy","year":"1995","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/S0022-0000(03)00120-X_BIB22","doi-asserted-by":"crossref","first-page":"268701","DOI":"10.1103\/PhysRevLett.89.268701","article-title":"Coloring random graphs","volume":"89","author":"Mulet","year":"2002","journal-title":"Phys. Rev. Lett."},{"issue":"1","key":"10.1016\/S0022-0000(03)00120-X_BIB23","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1006\/jctb.1996.0036","article-title":"Sudden emergence of a giant k-core in a random graph","volume":"67","author":"Pittel","year":"1996","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0022-0000(03)00120-X_BIB24","unstructured":"N. Wormald, Some problems in the enumeration of labelled graphs, Ph.D. Thesis, Newcastle University, 1978."},{"issue":"4","key":"10.1016\/S0022-0000(03)00120-X_BIB25","doi-asserted-by":"crossref","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","article-title":"Differential equations for random processes and random graphs","volume":"5","author":"Wormald","year":"1995","journal-title":"Ann. Appl. Probab."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S002200000300120X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S002200000300120X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T19:09:31Z","timestamp":1585163371000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S002200000300120X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,9]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,9]]}},"alternative-id":["S002200000300120X"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00120-x","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,9]]}}}