{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:31:21Z","timestamp":1767339081733,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031754081"},{"type":"electronic","value":"9783031754098"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-75409-8_3","type":"book-chapter","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:23Z","timestamp":1737497423000},"page":"35-49","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Independent Set Reconfiguration in\u00a0H-Free Graphs"],"prefix":"10.1007","author":[{"given":"Valentin","family":"Bartier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Bousquet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moritz","family":"M\u00fchlenthaler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,22]]},"reference":[{"key":"3_CR1","unstructured":"Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. In: Combinatorial-Algebraic Methods in Applied Mathematics, pp. 3\u201313 (1982)"},{"issue":"1\u20133","key":"3_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(02)00290-1","volume":"135","author":"VE Alekseev","year":"2004","unstructured":"Alekseev, V.E.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Appl. Math. 135(1\u20133), 3\u201316 (2004). https:\/\/doi.org\/10.1016\/S0166-218X(02)00290-1","journal-title":"Discrete Appl. Math."},{"key":"3_CR3","unstructured":"Bartier, V.: Combinatorial and algorithmic aspects of reconfiguration. Aspects combinatoires et algorithmiques de la Reconfiguration. Ph.D. thesis, Grenoble Alpes University, France (2021)"},{"issue":"9","key":"3_CR4","doi-asserted-by":"publisher","first-page":"2914","DOI":"10.1007\/S00453-021-00848-1","volume":"83","author":"V Bartier","year":"2021","unstructured":"Bartier, V., Bousquet, N., Dallard, C., Lomer, K., Mouawad, A.E.: On girth and the parameterized complexity of token sliding and token jumping. Algorithmica 83(9), 2914\u20132951 (2021). https:\/\/doi.org\/10.1007\/S00453-021-00848-1","journal-title":"Algorithmica"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Belavadi, M., Cameron, K., Merkel, O.: Reconfiguration of vertex colouring and forbidden induced subgraphs (2023)","DOI":"10.1016\/j.ejc.2023.103908"},{"issue":"4","key":"3_CR6","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/S00224-020-09967-8","volume":"65","author":"R Belmonte","year":"2021","unstructured":"Belmonte, R., Kim, E.J., Lampis, M., Mitsou, V., Otachi, Y., Sikora, F.: Token sliding on split graphs. Theory Comput. Syst. 65(4), 662\u2013686 (2021). https:\/\/doi.org\/10.1007\/S00224-020-09967-8","journal-title":"Theory Comput. Syst."},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-319-68705-6_10","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Bonamy","year":"2017","unstructured":"Bonamy, M., Bousquet, N.: Token sliding on chordal graphs. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 127\u2013139. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68705-6_10"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/J.JCTB.2022.10.005","volume":"159","author":"M Bonamy","year":"2023","unstructured":"Bonamy, M., Defrain, O., Klimosov\u00e1, T., Lagoutte, A., Narboni, J.: On Vizing\u2019s edge colouring question. J. Comb. Theory Ser. B 159, 126\u2013139 (2023). https:\/\/doi.org\/10.1016\/J.JCTB.2022.10.005","journal-title":"J. Comb. Theory Ser. B"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/J.DAM.2021.05.014","volume":"301","author":"M Bonamy","year":"2021","unstructured":"Bonamy, M., Dorbec, P., Ouvrard, P.: Dominating sets reconfiguration under token sliding. Discret. Appl. Math. 301, 6\u201318 (2021). https:\/\/doi.org\/10.1016\/J.DAM.2021.05.014","journal-title":"Discret. Appl. Math."},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/J.TCS.2020.05.033","volume":"838","author":"M Bonamy","year":"2020","unstructured":"Bonamy, M., et al.: Diameter of colorings under Kempe changes. Theor. Comput. Sci. 838, 45\u201357 (2020). https:\/\/doi.org\/10.1016\/J.TCS.2020.05.033","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"3_CR11","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1002\/JGT.21992","volume":"83","author":"PS Bonsma","year":"2016","unstructured":"Bonsma, P.S.: Independent set reconfiguration in cographs and their generalizations. J. Graph Theory 83(2), 164\u2013195 (2016). https:\/\/doi.org\/10.1002\/JGT.21992","journal-title":"J. Graph Theory"},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-319-08404-6_8","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"P Bonsma","year":"2014","unstructured":"Bonsma, P., Kami\u0144ski, M., Wrochna, M.: Reconfiguring independent sets in claw-free graphs. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 86\u201397. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-08404-6_8"},{"key":"3_CR13","doi-asserted-by":"publisher","unstructured":"Bousquet, N., Mouawad, A.E., Nishimura, N., Siebertz, S.: A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems. CoRR abs\/2204.10526 (2022). https:\/\/doi.org\/10.48550\/ARXIV.2204.10526","DOI":"10.48550\/ARXIV.2204.10526"},{"key":"3_CR14","doi-asserted-by":"publisher","unstructured":"Bousquet, N., Perarnau, G.: Fast recoloring of sparse graphs. Eur. J. Comb. 52, 1\u201311 (2016). https:\/\/doi.org\/10.1016\/J.EJC.2015.08.001","DOI":"10.1016\/J.EJC.2015.08.001"},{"issue":"1\u20133","key":"3_CR15","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/J.DISC.2004.06.019","volume":"288","author":"A Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A., Ho\u00e0ng, C.T., Vanherpe, J.: On minimal prime extensions of a four-vertex graph in a prime graph. Discret. Math. 288(1\u20133), 9\u201317 (2004). https:\/\/doi.org\/10.1016\/J.DISC.2004.06.019","journal-title":"Discret. Math."},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/J.TCS.2015.07.037","volume":"600","author":"ED Demaine","year":"2015","unstructured":"Demaine, E.D., et al.: Linear-time algorithm for sliding tokens on trees. Theor. Comput. Sci. 600, 132\u2013142 (2015). https:\/\/doi.org\/10.1016\/J.TCS.2015.07.037","journal-title":"Theor. Comput. Sci."},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"103319","DOI":"10.1016\/J.EJC.2021.103319","volume":"95","author":"Z Dvor\u00e1k","year":"2021","unstructured":"Dvor\u00e1k, Z., Feghali, C.: A Thomassen-type method for planar graph recoloring. Eur. J. Comb. 95, 103319 (2021). https:\/\/doi.org\/10.1016\/J.EJC.2021.103319","journal-title":"Eur. J. Comb."},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-662-48971-0_21","volume-title":"Algorithms and Computation","author":"E Fox-Epstein","year":"2015","unstructured":"Fox-Epstein, E., Hoang, D.A., Otachi, Y., Uehara, R.: Sliding token on bipartite permutation graphs. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 237\u2013247. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_21"},{"issue":"3","key":"3_CR19","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1016\/J.JCTB.2005.09.007","volume":"96","author":"MU Gerber","year":"2006","unstructured":"Gerber, M.U., Hertz, A., Lozin, V.V.: Augmenting chains in graphs without a skew star. J. Comb. Theory Ser. B 96(3), 352\u2013366 (2006). https:\/\/doi.org\/10.1016\/J.JCTB.2005.09.007","journal-title":"J. Comb. Theory Ser. B"},{"key":"3_CR20","doi-asserted-by":"publisher","unstructured":"Grzesik, A., Klimosov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on $$p_{6}$$-free graphs. ACM Trans. Algorithms 18(1), 4:1\u20134:57 (2022). https:\/\/doi.org\/10.1145\/3414473","DOI":"10.1145\/3414473"},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/J.TCS.2016.08.016","volume":"651","author":"A Haddadan","year":"2016","unstructured":"Haddadan, A., Ito, T., Mouawad, A.E., Nishimura, N., Ono, H., Suzuki, A., Tebbal, Y.: The complexity of dominating set reconfiguration. Theor. Comput. Sci. 651, 37\u201349 (2016). https:\/\/doi.org\/10.1016\/J.TCS.2016.08.016","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"3_CR22","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/J.TCS.2005.05.008","volume":"343","author":"RA Hearn","year":"2005","unstructured":"Hearn, R.A., Demaine, E.D.: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci. 343(1\u20132), 72\u201396 (2005). https:\/\/doi.org\/10.1016\/J.TCS.2005.05.008","journal-title":"Theor. Comput. Sci."},{"key":"3_CR23","doi-asserted-by":"publisher","unstructured":"van\u00a0den Heuvel, J.: The complexity of change. In: Blackburn, S.R., Gerke, S., Wildon, M. (eds.) Surveys in Combinatorics 2013. London Mathematical Society Lecture Note Series, vol.\u00a0409, pp. 127\u2013160. Cambridge University Press (2013). https:\/\/doi.org\/10.1017\/CBO9781139506748.005","DOI":"10.1017\/CBO9781139506748.005"},{"issue":"12\u201314","key":"3_CR24","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/J.TCS.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T., et al.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011). https:\/\/doi.org\/10.1016\/J.TCS.2010.12.005","journal-title":"Theor. Comput. Sci."},{"key":"3_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-319-13075-0_17","volume-title":"Algorithms and Computation","author":"T Ito","year":"2014","unstructured":"Ito, T., Kami\u0144ski, M., Ono, H.: Fixed-parameter tractability of token jumping on planar graphs. In: Ahn, H.-K., Shin, C.-S. (eds.) ISAAC 2014. LNCS, vol. 8889, pp. 208\u2013219. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-13075-0_17"},{"key":"3_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-319-06089-7_24","volume-title":"Theory and Applications of Models of Computation","author":"T Ito","year":"2014","unstructured":"Ito, T., Kami\u0144ski, M., Ono, H., Suzuki, A., Uehara, R., Yamanaka, K.: On the parameterized complexity for token jumping on graphs. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol. 8402, pp. 341\u2013351. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-06089-7_24"},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/J.DAM.2020.01.022","volume":"283","author":"T Ito","year":"2020","unstructured":"Ito, T., Kami\u0144ski, M., Ono, H., Suzuki, A., Uehara, R., Yamanaka, K.: Parameterized complexity of independent set reconfiguration problems. Discret. Appl. Math. 283, 336\u2013345 (2020). https:\/\/doi.org\/10.1016\/J.DAM.2020.01.022","journal-title":"Discret. Appl. Math."},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/J.TCS.2012.03.004","volume":"439","author":"M Kami\u0144ski","year":"2012","unstructured":"Kami\u0144ski, M., Medvedev, P., Milani\u010d, M.: Complexity of independent set reconfigurability problems. Theor. Comput. Sci. 439, 9\u201315 (2012). https:\/\/doi.org\/10.1016\/J.TCS.2012.03.004","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"3_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3280825","volume":"15","author":"D Lokshtanov","year":"2019","unstructured":"Lokshtanov, D., Mouawad, A.E.: The complexity of independent set reconfiguration on bipartite graphs. ACM Trans. Algorithms 15(1), 1\u201319 (2019). https:\/\/doi.org\/10.1145\/3280825","journal-title":"ACM Trans. Algorithms"},{"key":"3_CR30","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in $${P}_5$$-free graphs in polynomial time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 570\u2013581. SIAM (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.43","DOI":"10.1137\/1.9781611973402.43"},{"issue":"3","key":"3_CR31","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28(3), 284\u2013304 (1980). https:\/\/doi.org\/10.1016\/0095-8956(80)90074-X","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"3_CR32","doi-asserted-by":"publisher","first-page":"20","DOI":"10.3390\/A11020020","volume":"11","author":"AE Mouawad","year":"2018","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Siebertz, S.: Vertex cover reconfiguration and beyond. Algorithms 11(2), 20 (2018). https:\/\/doi.org\/10.3390\/A11020020","journal-title":"Algorithms"},{"issue":"1","key":"3_CR33","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/S00453-016-0159-2","volume":"78","author":"AE Mouawad","year":"2017","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. Algorithmica 78(1), 274\u2013297 (2017). https:\/\/doi.org\/10.1007\/S00453-016-0159-2","journal-title":"Algorithmica"},{"issue":"4","key":"3_CR34","doi-asserted-by":"publisher","first-page":"52","DOI":"10.3390\/A11040052","volume":"11","author":"N Nishimura","year":"2018","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52 (2018). https:\/\/doi.org\/10.3390\/A11040052","journal-title":"Algorithms"},{"issue":"1","key":"3_CR35","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Sbihi","year":"1980","unstructured":"Sbihi, N.: Algorithme de recherche d\u2019un stable de cardinalite maximum dans un graphe sans etoile. Discret. Math. 29(1), 53\u201376 (1980). https:\/\/doi.org\/10.1016\/0012-365X(90)90287-R","journal-title":"Discret. Math."},{"issue":"4","key":"3_CR36","doi-asserted-by":"publisher","first-page":"1182","DOI":"10.1007\/s10878-015-9947-x","volume":"32","author":"A Suzuki","year":"2016","unstructured":"Suzuki, A., Mouawad, A.E., Nishimura, N.: Reconfiguration of dominating sets. J. Comb. Optim. 32(4), 1182\u20131195 (2016). https:\/\/doi.org\/10.1007\/s10878-015-9947-x","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-75409-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:25Z","timestamp":1737497425000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-75409-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031754081","9783031754098"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-75409-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 January 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Gozd Martuljek","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovenia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conferences.famnit.upr.si\/event\/31\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}