{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T02:02:37Z","timestamp":1760061757450,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2015,6,24]],"date-time":"2015-06-24T00:00:00Z","timestamp":1435104000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["Grant Nos. DMS-1321794 and 1122374"],"award-info":[{"award-number":["Grant Nos. DMS-1321794 and 1122374"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2015,6,24]]},"DOI":"10.1145\/2755996.2756639","type":"proceedings-article","created":{"date-parts":[[2015,6,25]],"date-time":"2015-06-25T14:43:22Z","timestamp":1435243402000},"page":"133-140","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Graph-Coloring Ideals"],"prefix":"10.1145","author":[{"given":"Jes\u00fas A.","family":"De Loera","sequence":"first","affiliation":[{"name":"University of California, Davis, Davis, CA, USA"}]},{"given":"Susan","family":"Margulies","sequence":"additional","affiliation":[{"name":"United States Naval Academy, Annapolis, MD, USA"}]},{"given":"Michael","family":"Pernpeintner","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Munich, Germany"}]},{"given":"Eric","family":"Riedl","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, MA, USA"}]},{"given":"David","family":"Rolnick","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Gwen","family":"Spencer","sequence":"additional","affiliation":[{"name":"Smith College, Northampton, MA, USA"}]},{"given":"Despina","family":"Stasi","sequence":"additional","affiliation":[{"name":"University of Cyprus, Nicosia, Cyprus"}]},{"given":"Jon","family":"Swenson","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}]}],"member":"320","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Anintroduction to Gr\u00f6bner bases","author":"Adams W.","year":"1994","unstructured":"W. Adams and P. Loustaunau, \"Anintroduction to Gr\u00f6bner bases\", American Mathematical Society,Providence, Rhode Island, 1994."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/971651.971653"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01204715"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/910526"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-73.1.1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971361"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/791229.792263"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1726"},{"key":"e_1_3_2_1_9_1","unstructured":"D. Cifuentes and P. Parrilo \"Chordal Structure and Polynomial Systems\" manuscript available from math ArXiv:1411.1745."},{"key":"e_1_3_2_1_10_1","volume-title":"Springer Undergraduate texts inMathematics","author":"Cox D.","year":"1992","unstructured":"D. Cox, J. Little and D. O'Shea, \"Ideals,Varieties and Algorithms\", Springer Undergraduate texts inMathematics, Springer-Verlag, New York, 1992."},{"key":"e_1_3_2_1_11_1","first-page":"185","article-title":"Using Algebraic Geometry","author":"Cox D.","year":"1998","unstructured":"D. Cox, J. Little and D. O'Shea, \"Using Algebraic Geometry\", Springer Graduate Texts in Mathematics, 185, 1998.","journal-title":"Springer Graduate Texts in Mathematics"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.24033\/asens.2196"},{"issue":"1","key":"e_1_3_2_1_13_1","first-page":"89","article-title":"Gr\u00f6bner bases and graph colorings","volume":"36","author":"De Loera J. A.","year":"1995","unstructured":"J. A. De Loera, \"Gr\u00f6bner bases and graph colorings\", Beitrage zur Algebra und Geometrie, 36(1), pg. 89--96, 1995.","journal-title":"Beitrage zur Algebra und Geometrie"},{"key":"e_1_3_2_1_14_1","volume-title":"in \"Mixed Integer Non-Linear Programming","author":"De Loera J. A.","year":"2011","unstructured":"J. A. De Loera, P. Malkin, and P. Parrilo \"Computation with Polynomial Equations and Inequalities arising in Combinatorial Optimization\", in \"Mixed Integer Non-Linear Programming\" (J. Lee andS. Leyffer eds.), IMA Volumes in Mathematics and its Applications, Vol. 154. 1st Edition., 2011, X, 660 p.","edition":"1"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390768.1390797"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.08.007"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309009894"},{"key":"e_1_3_2_1_18_1","first-page":"173","article-title":"Graph theory","author":"Diestel R.","year":"2005","unstructured":"R. Diestel, \"Graph theory\", Springer Graduate Texts in Mathematics, 173, 2005.","journal-title":"Springer Graduate Texts in Mathematics"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219053"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1993.1051"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2512973"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/646671.699162"},{"key":"e_1_3_2_1_25_1","volume-title":"Academic Press","author":"Golumbic M. C.","year":"1980","unstructured":"M. C. Golumbic, \"Algorithmic graph theory and perfect graphs\", Academic Press, 1980."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.08.004"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the 2nd Israel Symposium on Theory and Computing Systems, pg. 250--260","author":"Khanna S.","year":"1993","unstructured":"S. Khanna, N. Linial, S. Safra, \"On thehardness of approximating the chromatic number\". Proceedings of the 2nd Israel Symposium on Theory and Computing Systems, pg. 250--260, 1993."},{"issue":"4","key":"e_1_3_2_1_28_1","first-page":"963","article-title":"Sharp effective Nullstellensatz","volume":"1","author":"Kollar J.","year":"1988","unstructured":"J. Kollar, \"Sharp effective Nullstellensatz\", J. of the AMS, 1(4), 963--975, 1988.","journal-title":"J. of the AMS"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1848"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)00057-X"},{"key":"e_1_3_2_1_32_1","first-page":"193","article-title":"Some algebraic methods for calculation of the number of colorings of a graph","volume":"293","author":"Matiyasevich Yu. V.","unstructured":"Yu. V. Matiyasevich. \"Some algebraic methods for calculation of the number of colorings of a graph\" (in Russian). Zapiski Nauchnykh Seminarov POMI, 293, pg. 193--205 (available via www.pdmi.ras.ru), 2001.","journal-title":"Zapiski Nauchnykh Seminarov POMI"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0447"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(82)90048-2"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837934.1837945"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/646671.699143"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56666-0_33"},{"key":"e_1_3_2_1_38_1","volume-title":"TU Munich","author":"Pernpeintner M.","year":"2014","unstructured":"M. Pernpeintner, On the Structure of Gr\u00f6bner Bases for Graph Coloring Ideals. Masters thesis, TU Munich, 2014."},{"key":"e_1_3_2_1_39_1","unstructured":"S. Ritscher \"Degree Bounds for Zero-dimensional Gr\u00f6bner Bases\" Master's Thesis 2009."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"}],"event":{"name":"ISSAC'15: International Symposium on Symbolic and Algebraic Computation","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"location":"Bath United Kingdom","acronym":"ISSAC'15"},"container-title":["Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2755996.2756639","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2755996.2756639","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:31Z","timestamp":1750230031000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2755996.2756639"}},"subtitle":["Nullstellensatz Certificates, Gr\u00f6bner Bases for Chordal Graphs, and Hardness of Gr\u00f6bner Bases"],"short-title":[],"issued":{"date-parts":[[2015,6,24]]},"references-count":39,"alternative-id":["10.1145\/2755996.2756639","10.1145\/2755996"],"URL":"https:\/\/doi.org\/10.1145\/2755996.2756639","relation":{},"subject":[],"published":{"date-parts":[[2015,6,24]]},"assertion":[{"value":"2015-06-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}