{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T08:28:36Z","timestamp":1721809716513},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,10,1]],"date-time":"2020-10-01T00:00:00Z","timestamp":1601510400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,10,1]],"date-time":"2020-10-01T00:00:00Z","timestamp":1601510400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00224-020-10014-9","type":"journal-article","created":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T05:02:21Z","timestamp":1604725341000},"page":"1307-1316","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fixed-Parameter Tractability of (n \u2212 k) List Coloring"],"prefix":"10.1007","volume":"64","author":[{"given":"Aritra","family":"Banik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashwin","family":"Jacob","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay Kumar","family":"Paliwal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,7]]},"reference":[{"key":"10014_CR1","doi-asserted-by":"crossref","unstructured":"Banik, A., Jacob, A., Paliwal, V.K., Raman, V.: Fixed-parameter tractability of (n \u2212k) list coloring. In: International workshop on combinatorial algorithms, pp 61\u201369. Springer (2019)","DOI":"10.1007\/978-3-030-25005-8_6"},{"issue":"3","key":"10014_CR2","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976). https:\/\/doi.org\/10.1016\/0304-3975(76)90059-1","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10014_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0012-365X(80)90236-8","volume":"30","author":"DP Dailey","year":"1980","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","journal-title":"Discret. Math."},{"key":"10014_CR4","doi-asserted-by":"crossref","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)"},{"key":"10014_CR5","doi-asserted-by":"crossref","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)","journal-title":"Inf. Comput."},{"issue":"3","key":"10014_CR6","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discret. Appl. Math. 127(3), 415\u2013429 (2003). https:\/\/doi.org\/10.1016\/S0166-218X(02)00242-1","journal-title":"Discret. Appl. Math."},{"key":"10014_CR7","doi-asserted-by":"publisher","unstructured":"Paulusma, D.: Open problems on graph coloring for special graph classes. In: Graph-theoretic concepts in computer science - 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015, Revised Papers, pp 16\u201330. https:\/\/doi.org\/10.1007\/978-3-662-53174-7_2 (2015)","DOI":"10.1007\/978-3-662-53174-7_2"},{"issue":"2","key":"10014_CR8","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143\u2013153 (2011)","journal-title":"Inf. Comput."},{"key":"10014_CR9","doi-asserted-by":"crossref","unstructured":"Chor, B., Fellows, M., Juedes, D.: Linear kernels in linear time, or how to save k colors in O(n2) steps. In: International workshop on graph-theoretic concepts in computer science, pp 257\u2013269. Springer (2004)","DOI":"10.1007\/978-3-540-30559-0_22"},{"key":"10014_CR10","doi-asserted-by":"crossref","unstructured":"Arora, P., Banik, A., Paliwal, V.K., Raman, V.: Some (in) tractable parameterizations of coloring and list-coloring. In: International workshop on frontiers in algorithmics, pp 126\u2013139. Springer (2018)","DOI":"10.1007\/978-3-319-78455-7_10"},{"key":"10014_CR11","volume-title":"Graph theory, 4th edition, Graduate texts in mathematics, vol. 173","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph theory, 4th edition, Graduate texts in mathematics, vol. 173. Springer, Berlin (2012)"},{"issue":"4","key":"10014_CR12","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973). https:\/\/doi.org\/10.1137\/0202019","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10014_CR13","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"10014_CR14","unstructured":"Gutin, G., Majumdar, D., Ordyniak, S., Wahlstr\u00f6m, M: Parameterized pre-coloring extension and list coloring problems. In: 37th International symposium on theoretical aspects of computer science (STACS 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2020)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10014-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-020-10014-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10014-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,12]],"date-time":"2020-11-12T10:18:41Z","timestamp":1605176321000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-020-10014-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10]]},"references-count":14,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["10014"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-10014-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10]]},"assertion":[{"value":"11 October 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 November 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}