{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:55Z","timestamp":1759638715351},"reference-count":9,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information Processing Letters"],"published-print":{"date-parts":[[1997,1]]},"DOI":"10.1016\/s0020-0190(96)00190-1","type":"journal-article","created":{"date-parts":[[2003,4,7]],"date-time":"2003-04-07T13:32:24Z","timestamp":1049722344000},"page":"49-53","source":"Crossref","is-referenced-by-count":83,"title":["An algorithm for 3-colorable graphs"],"prefix":"10.1016","volume":"61","author":[{"given":"Avrim","family":"Blum","sequence":"first","affiliation":[]},{"given":"David","family":"Karger","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0020-0190(96)00190-1_BIB1","first-page":"27","article-title":"A local-ratio theorem for approximating the weighted vertex cover problem","volume":"25","author":"Bar-Yehuda","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/S0020-0190(96)00190-1_BIB2","series-title":"Proc. 21st Ann. ACM Symp. on Theory of Computing","first-page":"535","article-title":"An \u00d5(n0.4)-approximation algorithm for 3-coloring (and improved approximation algorithms for k-coloring)","author":"Blum","year":"1989"},{"issue":"3","key":"10.1016\/S0020-0190(96)00190-1_BIB3","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1145\/176584.176586","article-title":"New approximation algorithms for graph coloring","volume":"31","author":"Blum","year":"1994","journal-title":"J. ACM"},{"key":"10.1016\/S0020-0190(96)00190-1_BIB4","series-title":"Proc. 26th ACM Symp. on Theory of Computing","first-page":"184","article-title":"Improved non-approximability results","author":"Bellare","year":"1994"},{"key":"10.1016\/S0020-0190(96)00190-1_BIB5","series-title":"Proc. 2nd Israeli Symp. on Theory and Computing Systems","first-page":"250","article-title":"On the hardness of approximating the chromatic number","author":"Khanna","year":"1992"},{"key":"10.1016\/S0020-0190(96)00190-1_BIB6","series-title":"Proc. 35th Ann. Symp. on Foundations of Computer Science","article-title":"Approximate graph coloring by semidefinite programming","author":"Karger","year":"1994"},{"key":"10.1016\/S0020-0190(96)00190-1_BIB7","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF00290149","article-title":"Ramsey numbers and an approximation algorithm for the vertex cover problem","volume":"22","author":"Monien","year":"1985","journal-title":"Acta Inform."},{"key":"10.1016\/S0020-0190(96)00190-1_BIB8","series-title":"Proc. 21st Internat. Workshop on Graph Theoretic Concepts in Computer Science","first-page":"146","article-title":"An approximation algorithm for 3-colorability","volume":"Vol. 1017","author":"Schiermeyer","year":"1995"},{"issue":"4","key":"10.1016\/S0020-0190(96)00190-1_BIB9","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1145\/2157.2158","article-title":"Improving the performance guarantee for approximate graph coloring","volume":"30","author":"Wigderson","year":"1983","journal-title":"J. ACM"}],"container-title":["Information Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019096001901?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019096001901?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T12:53:47Z","timestamp":1556628827000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0020019096001901"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["S0020019096001901"],"URL":"https:\/\/doi.org\/10.1016\/s0020-0190(96)00190-1","relation":{},"ISSN":["0020-0190"],"issn-type":[{"value":"0020-0190","type":"print"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}