{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:16Z","timestamp":1784568316641,"version":"3.55.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T00:00:00Z","timestamp":1556841600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["Veni grant \u2018Frontiers in Parameterized Preprocessing\u2019"],"award-info":[{"award-number":["Veni grant \u2018Frontiers in Parameterized Preprocessing\u2019"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["Gravitation grant: \u2018NETWORKS\u2019"],"award-info":[{"award-number":["Gravitation grant: \u2018NETWORKS\u2019"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["Gravitation grant: \u2018NETWORKS\u2019"],"award-info":[{"award-number":["Gravitation grant: \u2018NETWORKS\u2019"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s00453-019-00578-5","type":"journal-article","created":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T07:02:50Z","timestamp":1556866970000},"page":"3865-3889","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8204-1268","authenticated-orcid":false,"given":"Bart M. P.","family":"Jansen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3721-6721","authenticated-orcid":false,"given":"Astrid","family":"Pieterse","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,5,3]]},"reference":[{"issue":"1","key":"578_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014). \n                    https:\/\/doi.org\/10.1137\/120880240","journal-title":"SIAM J. Discrete Math."},{"key":"578_CR2","doi-asserted-by":"publisher","unstructured":"Bougeret, M., Sau, I.: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? In: Proceedings of 12th IPEC, pp. 10:1\u201310:13 (2017). \n                    https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.10","DOI":"10.4230\/LIPIcs.IPEC.2017.10"},{"issue":"1","key":"578_CR3","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/s00453-016-0139-6","volume":"78","author":"R Chitnis","year":"2017","unstructured":"Chitnis, R., Egri, L., Marx, D.: List H-coloring a graph by removing few vertices. Algorithmica 78(1), 110\u2013146 (2017). \n                    https:\/\/doi.org\/10.1007\/s00453-016-0139-6","journal-title":"Algorithmica"},{"key":"578_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"578_CR5","doi-asserted-by":"crossref","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: Proceedings of 23th SODA, SODA \u201912, pp. 68\u201381 (2012)","DOI":"10.1137\/1.9781611973099.6"},{"issue":"4","key":"578_CR6","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1\u201323:27 (2014). \n                    https:\/\/doi.org\/10.1145\/2629620","journal-title":"J. ACM"},{"key":"578_CR7","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013). \n                    https:\/\/doi.org\/10.1007\/978-1-4471-5559-1","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"23","key":"578_CR8","doi-asserted-by":"publisher","first-page":"2513","DOI":"10.1016\/j.tcs.2010.10.043","volume":"412","author":"J Fiala","year":"2011","unstructured":"Fiala, J., Golovach, P.A., Kratochv\u00edl, J.: Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor. Comput. Sci. 412(23), 2513\u20132523 (2011). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2010.10.043","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"578_CR9","first-page":"77","volume":"17","author":"R Ganian","year":"2015","unstructured":"Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17(2), 77\u2013100 (2015)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"1","key":"578_CR10","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. J. Comb. Theory Ser. B 48(1), 92\u2013110 (1990). \n                    https:\/\/doi.org\/10.1016\/0095-8956(90)90132-J","journal-title":"J. Comb. Theory Ser. B"},{"key":"578_CR11","doi-asserted-by":"publisher","unstructured":"Hols, E.M.C., Kratsch, S.: Smaller parameters for vertex cover kernelization. In: Proceedings of 12th IPEC, pp. 20:1\u201320:12 (2017). \n                    https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.20","DOI":"10.4230\/LIPIcs.IPEC.2017.20"},{"key":"578_CR12","doi-asserted-by":"publisher","unstructured":"Jaffke, L., Jansen, B.M.P.: Fine-grained parameterized complexity analysis of graph coloring problems. In: Proceedings of 10th CIAC, pp. 345\u2013356 (2017). \n                    https:\/\/doi.org\/10.1007\/978-3-319-57586-5_29","DOI":"10.1007\/978-3-319-57586-5_29"},{"key":"578_CR13","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.ic.2013.08.005","volume":"231","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Kratsch, S.: Data reduction for graph coloring problems. Inf. Comput. 231, 70\u201388 (2013). \n                    https:\/\/doi.org\/10.1016\/j.ic.2013.08.005","journal-title":"Inf. Comput."},{"key":"578_CR14","doi-asserted-by":"publisher","unstructured":"Jansen, B.M.P., Pieterse, A.: Optimal sparsification for some binary CSPs using low-degree polynomials. In: Proceedings of 41st MFCS, pp. 71:1\u201371:14 (2016). \n                    https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.71","DOI":"10.4230\/LIPIcs.MFCS.2016.71"},{"issue":"1","key":"578_CR15","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-016-0189-9","volume":"79","author":"BMP Jansen","year":"2017","unstructured":"Jansen, B.M.P., Pieterse, A.: Sparsification upper and lower bounds for graph problems and not-all-equal SAT. Algorithmica 79(1), 3\u201328 (2017). \n                    https:\/\/doi.org\/10.1007\/s00453-016-0189-9","journal-title":"Algorithmica"},{"issue":"3","key":"578_CR16","doi-asserted-by":"publisher","first-page":"40:1","DOI":"10.1145\/2832912","volume":"12","author":"S Kratsch","year":"2016","unstructured":"Kratsch, S., Philip, G., Ray, S.: Point line cover: the easy kernel is essentially tight. ACM Trans. Algorithms 12(3), 40:1\u201340:16 (2016). \n                    https:\/\/doi.org\/10.1145\/2832912","journal-title":"ACM Trans. Algorithms"},{"key":"578_CR17","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019","volume-title":"Efficient Graph Representations","author":"JP Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. American Mathematical Society, Providence (2003)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00578-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00578-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00578-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,1]],"date-time":"2020-05-01T23:14:57Z","timestamp":1588374897000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00578-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,3]]},"references-count":17,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["578"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00578-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,3]]},"assertion":[{"value":"23 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}