{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T21:13:43Z","timestamp":1772313223460,"version":"3.50.1"},"reference-count":52,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100014013","name":"UK Research and Innovation","doi-asserted-by":"publisher","award":["EP\/X024431\/1"],"award-info":[{"award-number":["EP\/X024431\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,8,31]]},"DOI":"10.1137\/24m1691594","type":"journal-article","created":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T08:00:38Z","timestamp":1755676838000},"page":"1138-1192","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Graph Coloring and the Crystal with a Hollow Shadow"],"prefix":"10.1137","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9491-2016","authenticated-orcid":true,"given":"Lorenzo","family":"Ciardo","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD Oxford, UK."}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":true,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD Oxford, UK."}]}],"member":"351","published-online":{"date-parts":[[2025,8,20]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1982-029-3"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a002"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006507"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exu070"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/3457606"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2010.11.019"},{"key":"ref15","volume":"24","author":"Bhangale A.","year":"2022","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/19M128212X"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.46298\/theoretics.23.2"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/20M1312745"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1145\/3470867"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(03)00429-4"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4543-4_6"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2017.11.005"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2021.01.001"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107325708"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1145\/2873054"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1145\/2811255"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2016.08.020"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(92)90015-M"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1137\/22M1476435"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.06.013"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2008.05.019"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.831"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a010"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376794"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(72)90057-3"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(00)00071-9"},{"key":"ref64","first-page":"393","volume":"20","author":"Khanna S.","year":"2000","journal-title":"Comb."},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1137\/17M1152966"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1137\/20M1378223"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400380079"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"ref75","first-page":"12","volume":"13","author":"Nakajima T.-V.","year":"2022","journal-title":"ACM Trans. Comput. Theory"},{"key":"ref76","volume-title":"Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization","author":"Parrilo P. A.","year":"2000"},{"key":"ref77","first-page":"209","volume":"32","author":"Poljak S.","year":"1991","journal-title":"Comment. Math. Univ. Carol."},{"key":"ref78","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1957-044-3"},{"key":"ref81","series-title":"Wiley-Interscience Series in Discrete Mathematics","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","year":"1986"},{"key":"ref82","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","year":"1998"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070233"},{"key":"ref86","doi-asserted-by":"publisher","DOI":"10.1145\/2157.2158"},{"key":"ref87","first-page":"1","volume":"3","author":"Zeilberger D.","year":"1996","journal-title":"Electron. J. Combin."},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.11650\/twjm\/1500406890"},{"key":"ref90","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T08:00:40Z","timestamp":1755676840000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1691594"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,20]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,31]]}},"alternative-id":["10.1137\/24M1691594"],"URL":"https:\/\/doi.org\/10.1137\/24m1691594","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,20]]}}}