{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T21:12:30Z","timestamp":1743109950708,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031095733"},{"type":"electronic","value":"9783031095740"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-09574-0_4","type":"book-chapter","created":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T17:36:07Z","timestamp":1656005767000},"page":"46-63","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of\u00a0List Coloring and\u00a0Max Coloring"],"prefix":"10.1007","author":[{"given":"Bardiya","family":"Aryanfard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,24]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","unstructured":"Adleman, L.M., Jr., H.W.L.: Finding irreducible polynomials over finite fields. In: Hartmanis, J. (ed.) Proceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, California, USA, 28\u201330 May 1986, pp. 350\u2013355. ACM (1986). https:\/\/doi.org\/10.1145\/12130.12166","DOI":"10.1145\/12130.12166"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.tcs.2018.03.013","volume":"729","author":"J Ara\u00fajo","year":"2018","unstructured":"Ara\u00fajo, J., Baste, J., Sau, I.: Ruling out FPT algorithms for weighted coloring on forests. Theor. Comput. Sci. 729, 11\u201319 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.03.013","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"4_CR3","doi-asserted-by":"publisher","first-page":"2029","DOI":"10.1137\/140954167","volume":"28","author":"J Ara\u00fajo","year":"2014","unstructured":"Ara\u00fajo, J., Nisse, N., P\u00e9rennes, S.: Weighted coloring in trees. SIAM J. Discret. Math. 28(4), 2029\u20132041 (2014). https:\/\/doi.org\/10.1137\/140954167","journal-title":"SIAM J. Discret. Math."},{"key":"4_CR4","unstructured":"Bannach, M., et al.: Solving packing problems with few small items using rainbow matchings. arXiv abs\/2007.02660 (2020)"},{"key":"4_CR5","doi-asserted-by":"publisher","unstructured":"Dailey, D.P.: Uniqueness of colorability and colorability of planar 4-regular graphs are np-complete. Discret. Math. 30(3), 289\u2013293 (1980). https:\/\/doi.org\/10.1016\/0012-365X(80)90236-8. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0012365X80902368","DOI":"10.1016\/0012-365X(80)90236-8"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-36379-3_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Demange","year":"2002","unstructured":"Demange, M., Werra, D., Monnot, J., Paschos, V.T.: Weighted node coloring: when stable sets are expensive. In: Goos, G., Hartmanis, J., van Leeuwen, J., Ku\u010dera, L. (eds.) WG 2002. LNCS, vol. 2573, pp. 114\u2013125. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-36379-3_11"},{"issue":"4","key":"4_CR7","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"RA DeMillo","year":"1978","unstructured":"DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Process. Lett. 7(4), 193\u2013195 (1978). https:\/\/doi.org\/10.1016\/0020-0190(78)90067-4","journal-title":"Inf. Process. Lett."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.tcs.2018.08.002","volume":"758","author":"B Escoffier","year":"2019","unstructured":"Escoffier, B.: Saving colors and max coloring: some fixed-parameter tractability results. Theor. Comput. Sci. 758, 30\u201341 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2018.08.002","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"4_CR9","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.ipl.2005.09.013","volume":"97","author":"B Escoffier","year":"2006","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring: further complexity and approximability results. Inf. Process. Lett. 97(3), 98\u2013103 (2006). https:\/\/doi.org\/10.1016\/j.ipl.2005.09.013","journal-title":"Inf. Process. Lett."},{"issue":"23","key":"4_CR10","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). https:\/\/doi.org\/10.1016\/j.tcs.2010.10.043","journal-title":"Theor. Comput. Sci."},{"key":"4_CR11","doi-asserted-by":"publisher","unstructured":"Gutin, G., Wahlstr\u00f6m, M., Yeo, A.: Rural postman parameterized by the number of components of required edges. J. Comput. Syst. Sci. 83(1), 121\u2013131 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2016.06.001. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000016300411","DOI":"10.1016\/j.jcss.2016.06.001"},{"issue":"1","key":"4_CR12","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1137\/20M1323369","volume":"35","author":"GZ Gutin","year":"2021","unstructured":"Gutin, G.Z., Majumdar, D., Ordyniak, S., Wahlstr\u00f6m, M.: Parameterized pre-coloring extension and list coloring problems. SIAM J. Discret. Math. 35(1), 575\u2013596 (2021). https:\/\/doi.org\/10.1137\/20M1323369","journal-title":"SIAM J. Discret. Math."},{"key":"4_CR13","doi-asserted-by":"publisher","unstructured":"Impagliazzo, R., Paturi, R.: Complexity of k-SAT. In: Proceedings of Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat. No. 99CB36317), pp. 237\u2013240 (1999). https:\/\/doi.org\/10.1109\/CCC.1999.766282","DOI":"10.1109\/CCC.1999.766282"},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010). https:\/\/doi.org\/10.4086\/toc.2010.v006a005","journal-title":"Theory Comput."},{"issue":"4","key":"4_CR15","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980). https:\/\/doi.org\/10.1145\/322217.322225","journal-title":"J. ACM"},{"key":"4_CR16","doi-asserted-by":"publisher","unstructured":"Wahlstr\u00f6m, M.: Abusing the tutte matrix: an algebraic instance compression for the k-set-cycle problem. In: Portier, N., Wilke, T. (eds.) 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, Kiel, Germany, 27 February\u20132 March 2013. LIPIcs, vol. 20, pp. 341\u2013352. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2013). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2013.341","DOI":"10.4230\/LIPIcs.STACS.2013.341"},{"issue":"4","key":"4_CR17","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1016\/j.dam.2008.06.013","volume":"157","author":"D de Werra","year":"2009","unstructured":"de Werra, D., Demange, M., Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring on planar, bipartite and split graphs: complexity and approximation. Discret. Appl. Math. 157(4), 819\u2013832 (2009). https:\/\/doi.org\/10.1016\/j.dam.2008.06.013","journal-title":"Discret. Appl. Math."},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and Algebraic Computation. LNCS, vol. 72, pp. 216\u2013226. Springer, Heidelberg (1979). https:\/\/doi.org\/10.1007\/3-540-09519-5_73"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-09574-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,26]],"date-time":"2022-06-26T23:03:22Z","timestamp":1656284602000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-09574-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031095733","9783031095740"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-09574-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"24 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"St. Petersburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}