{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:28Z","timestamp":1740107128565,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T00:00:00Z","timestamp":1727913600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T00:00:00Z","timestamp":1727913600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board, India","doi-asserted-by":"crossref","award":["MTR\/2023\/000364"],"award-info":[{"award-number":["MTR\/2023\/000364"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s00373-024-02837-x","type":"journal-article","created":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T09:02:03Z","timestamp":1727946123000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of Near-3-Choosability Problem"],"prefix":"10.1007","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8393-9109","authenticated-orcid":false,"given":"Sounaka","family":"Mishra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Rohini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sagar S.","family":"Sawant","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,3]]},"reference":[{"key":"2837_CR1","unstructured":"Erdos, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Proceedings West Coast Conf. on Combinatorics. Graph Theory and Computing, Congressus Numerantium, vol. 26, pp. 125\u2013157 (1979)"},{"key":"2837_CR2","doi-asserted-by":"publisher","DOI":"10.37236\/6738","author":"H Choi","year":"2017","unstructured":"Choi, H., Kwon, Y.: On t-common list-colorings. Electron. J. Combin. (2017). https:\/\/doi.org\/10.37236\/6738","journal-title":"Electron. J. Combin."},{"key":"2837_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.07.006","author":"X Zhu","year":"2019","unstructured":"Zhu, X.: A refinement of choosability of graphs. J. Combin. Theory Ser. B (2019). https:\/\/doi.org\/10.1016\/j.jctb.2019.07.006","journal-title":"J. Combin. Theory Ser. B"},{"key":"2837_CR4","first-page":"109","volume":"8","author":"H Grotzsch","year":"1959","unstructured":"Grotzsch, H.: Ein dreifarbensatz fur dreikreisfreie netze auf der kugel. Wiss. Z. Martin Luther Univ. Halle-Wittenberg Math. Nat. Reihe. 8, 109\u2013120 (1959)","journal-title":"Wiss. Z. Martin Luther Univ. Halle-Wittenberg Math. Nat. Reihe."},{"issue":"1","key":"2837_CR5","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0012-365X(94)00180-9","volume":"146","author":"M Voigt","year":"1995","unstructured":"Voigt, M.: A not 3-choosable planar graph without 3-cycles. Discrete Math. 146(1), 325\u2013328 (1995). https:\/\/doi.org\/10.1016\/0012-365X(94)00180-9","journal-title":"Discrete Math."},{"issue":"1","key":"2837_CR6","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0012-365X(95)00104-5","volume":"159","author":"S Gutner","year":"1996","unstructured":"Gutner, S.: The complexity of planar graph choosability. Discrete Math. 159(1), 119\u2013130 (1996). https:\/\/doi.org\/10.1016\/0012-365X(95)00104-5","journal-title":"Discrete Math."},{"issue":"2","key":"2837_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/j.disc.2004.10.015","volume":"290","author":"AN Glebov","year":"2005","unstructured":"Glebov, A.N., Kostochka, A.V., Tashkinov, V.A.: Smaller planar triangle-free graphs that are not 3-list-colorable. Discrete Math. 290(2), 269\u2013274 (2005). https:\/\/doi.org\/10.1016\/j.disc.2004.10.015","journal-title":"Discrete Math."},{"issue":"4","key":"2837_CR8","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/jgt.22028","volume":"84","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of coloring graphs with forbidden subgraphs. J. Graph Theory 84(4), 331\u2013363 (2017)","journal-title":"J. Graph Theory"},{"issue":"1","key":"2837_CR9","doi-asserted-by":"publisher","first-page":"46","DOI":"10.37236\/1799","volume":"11","author":"A Farrugia","year":"2004","unstructured":"Farrugia, A.: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Combin. 11(1), 46\u20139 (2004). https:\/\/doi.org\/10.37236\/1799","journal-title":"Electron. J. Combin."},{"key":"2837_CR10","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.ipl.2017.11.004","volume":"131","author":"M Bonamy","year":"2018","unstructured":"Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M., Paulusma, D.: Independent feedback vertex sets for graphs of bounded diameter. Inform. Process. Lett. 131, 26\u201332 (2018). https:\/\/doi.org\/10.1016\/j.ipl.2017.11.004","journal-title":"Inform. Process. Lett."},{"issue":"12","key":"2837_CR11","doi-asserted-by":"publisher","first-page":"1207","DOI":"10.1016\/j.disc.2005.09.016","volume":"306","author":"A Yang","year":"2006","unstructured":"Yang, A., Yuan, J.: Partition the vertices of a graph into one independent set and one acyclic set. Discrete Math. 306(12), 1207\u20131216 (2006). https:\/\/doi.org\/10.1016\/j.disc.2005.09.016","journal-title":"Discrete Math."},{"key":"2837_CR12","doi-asserted-by":"publisher","unstructured":"Tamura, Y., Ito, T., Zhou, X.: Minimization and parameterized variants of vertex partition problems on graphs. In: Cao, Y., Cheng, S.-W., Li, M. (eds.) 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, pp. 40\u201314013. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2020.40. https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ISAAC.2020.40","DOI":"10.4230\/LIPIcs.ISAAC.2020.40"},{"issue":"4","key":"2837_CR13","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. 27(4), 942\u2013959 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2837_CR14","doi-asserted-by":"publisher","first-page":"371","DOI":"10.4007\/annals.2009.170.371","volume":"170","author":"N Alon","year":"2009","unstructured":"Alon, N., Shapira, A., Sudakov, B.: Additive approximation for edge-deletion problems. Ann. Math. 170(1), 371\u2013411 (2009)","journal-title":"Ann. Math."},{"key":"2837_CR15","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 174. Freeman, San Francisco (1979)"},{"issue":"2","key":"2837_CR16","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"2837_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.5486\/PMD.1949.1.1.01","volume":"1","author":"PE Os","year":"2022","unstructured":"Os, P.E., P\u00f3sa, L.: On the maximal number of disjoint circuits of a graph. Publ Math Debrecen 1, 1 (2022)","journal-title":"Publ Math Debrecen"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02837-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02837-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02837-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T20:06:40Z","timestamp":1733515600000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02837-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,3]]},"references-count":17,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["2837"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02837-x","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2024,10,3]]},"assertion":[{"value":"12 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"104"}}