{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:56:06Z","timestamp":1787324166768,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Golovach, Paulusma, and Song [ Inform. and Comput., 237 (2014), pp. 204--214] asked to determine the parameterized complexity of the following problems parameterized by $k$: 1. Given a graph $G$, a clique modulator $D$ (a clique modulator is a set of vertices, whose removal results in a clique) of size $k$ for $G$, and a list $L(v)$ of colors for every $v\\in V(G)$, decide whether $G$ has a proper list coloring. 2. Given a graph $G$, a clique modulator $D$ of size $k$ for $G$, and a pre-coloring $\\lambda_P: X \\rightarrow Q$ for $X \\subseteq V(G),$ decide whether $\\lambda_P$ can be extended to a proper coloring of $G$ using only colors from $Q$. For problem 1 we design an ${\\mathcal O}^*(2^k)$-time randomized algorithm and for problem 2 we obtain a kernel with at most $3k$ vertices. Banik et al. [in Proceedings of IWOCA 2019, Springer, Berlin, 2019, pp. 61--69] proved the following problem is fixed-parameter tractable and asked whether it admits a polynomial kernel: Given a graph $G$, an integer $k$, and a list $L(v)$ of exactly $n-k$ colors for every $v \\in V(G),$ decide whether there is a proper list coloring for $G$. We obtain a kernel with ${\\mathcal O}(k^2)$ vertices and colors and a compression to a variation of the problem with ${\\mathcal O}(k)$ vertices and ${\\mathcal O}(k^2)$ colors.<\/jats:p>","DOI":"10.1137\/20m1323369","type":"journal-article","created":{"date-parts":[[2021,3,29]],"date-time":"2021-03-29T10:54:32Z","timestamp":1617015272000},"page":"575-596","source":"Crossref","is-referenced-by-count":9,"title":["Parameterized Pre-Coloring Extension and List Coloring Problems"],"prefix":"10.1137","volume":"35","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2677-4648","authenticated-orcid":true,"given":"Diptapriyo","family":"Majumdar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1935-651X","authenticated-orcid":true,"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,3,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9428-7"},{"key":"atypb2","first-page":"126","author":"Arora P.","year":"2018","journal-title":"Berlin"},{"key":"atypb3","first-page":"61","author":"Banik A.","year":"2019","journal-title":"Berlin"},{"key":"atypb4","first-page":"185","volume":"30","author":"Berend D.","year":"2010","journal-title":"Probab. Math. Statist."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.03.003"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9981-1"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.006"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0331751-8"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00242-1"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"atypb12","first-page":"257","author":"Chor B.","year":"2004","journal-title":"New York"},{"key":"atypb13","first-page":"291","author":"Chudnovsky M.","year":"2014","journal-title":"South Korea"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 4th ed., Grad. Texts in Math. 173, Springer, Heidelberg, 2010.","DOI":"10.1007\/978-3-642-14279-6"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/2650261"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"R. Downey and M. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Springer, New York, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.08.002"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"F. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi,\n                      Kernelization\n                      , Cambridge University Press, Cambridge, UK, 2019.","DOI":"10.1017\/9781107415157"},{"key":"atypb21","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, San Francisco, CA, 1979."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22028"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.02.004"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0189-9"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"T. R. Jensen and B. Toft,\n                      Graph Coloring Problems\n                      , John Wiley & Sons, New York, 1995.","DOI":"10.1002\/9781118032497"},{"key":"atypb26","first-page":"1375","author":"Koutis I.","year":"2016","journal-title":"New York"},{"key":"atypb27","unstructured":"R. Krauthgamer and O. Trabelsi,\n                      The set cover conjecture and subgraph isomorphism with a tree pattern\n                      , in Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, R. Niedermeier and C. Paul, eds., LIPIcs. Leibniz Int. Proc. Inform. 126, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2019, 45,https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.45."},{"key":"atypb28","first-page":"3","author":"Lov\u00e1sz L.","year":"1973","journal-title":"Canada"},{"key":"atypb29","first-page":"17","author":"Micali S.","year":"1980","journal-title":"Washington, DC"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"D. Paulusma,\n                      Open problems on graph coloring for special graph classes\n                      , in Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015, Garching, Germany, Revised Papers, E. W. Mayr, ed., Lecture Notes in Comput. Sci. 9224, Springer, Berlin, 2015, pp. 16-30.","DOI":"10.1007\/978-3-662-53174-7_2"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-003-0540-1"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1049"},{"key":"atypb34","unstructured":"M. Wahlstr\u00f6m,\n                      Abusing the Tutte matrix: An algebraic instance compression for the $K$-set-cycle problem\n                      , in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, Kiel, Germany, N. Portier and T. Wilke, eds., LIPIcs. Leibniz Int. Proc. Inform. 20, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2013, pp. 341-352."},{"key":"atypb35","unstructured":"F. Yates,\n                      The Design and Analysis of Factorial Experiments\n                      , Technical Communication 35, Commonwealth Bureau of Soils, 1937."},{"key":"atypb36","first-page":"216","author":"Zippel R.","year":"1979","journal-title":"New York"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1323369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:19:45Z","timestamp":1787321985000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1323369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1323369"],"URL":"https:\/\/doi.org\/10.1137\/20m1323369","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}