{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:28Z","timestamp":1770994048266,"version":"3.50.1"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031643088","type":"print"},{"value":"9783031643095","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-64309-5_19","type":"book-chapter","created":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T22:01:49Z","timestamp":1719871309000},"page":"233-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Graph Homomorphism, Monotone Classes and\u00a0Bounded Pathwidth"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-0346-7032","authenticated-orcid":false,"given":"Tala","family":"Eagling-Vose","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4642-8614","authenticated-orcid":false,"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5945-9287","authenticated-orcid":false,"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0797-0512","authenticated-orcid":false,"given":"Siani","family":"Smith","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,2]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.tcs.2007.09.013","volume":"389","author":"VE Alekseev","year":"2007","unstructured":"Alekseev, V.E., Boliac, R., Korobitsyn, D.V., Lozin, V.V.: NP-hard graph problems and boundary classes of graphs. Theor. Comput. Sci. 389, 219\u2013236 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR2","first-page":"90","volume":"2","author":"VE Alekseev","year":"1990","unstructured":"Alekseev, V.E., Korobitsyn, D.V.: Complexity of some problems on hereditary graph classes. Diskret. Mat. 2, 90\u201396 (1990)","journal-title":"Diskret. Mat."},{"issue":"7","key":"19_CR3","doi-asserted-by":"publisher","first-page":"1415","DOI":"10.1016\/j.jcss.2014.04.014","volume":"80","author":"A Atserias","year":"2014","unstructured":"Atserias, A., Oliva, S.: Bounded-width QBF is pspace-complete. J. Comput. Syst. Sci. 80(7), 1415\u20131429 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1142\/S0129054191000091","volume":"2","author":"HL Bodlaender","year":"1991","unstructured":"Bodlaender, H.L.: On the complexity of some coloring games. Int. J. Found. Comput. Sci. 2, 133\u2013147 (1991)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"19_CR5","unstructured":"Bodlaender, H.L., et al.: Complexity framework for forbidden subgraphs IV: the steiner forest problem. CoRR, abs\/2305.01613, 2023"},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/3-540-36136-7_5","volume-title":"Algorithms and Computation","author":"R Boliac","year":"2002","unstructured":"Boliac, R., Lozin, V.: On the clique-width of graphs in hereditary classes. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 44\u201354. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-36136-7_5"},{"issue":"9","key":"19_CR7","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1016\/j.ic.2009.05.003","volume":"207","author":"F B\u00f6rner","year":"2009","unstructured":"B\u00f6rner, F., Bulatov, A.A., Chen, H., Jeavons, P., Krokhin, A.A.: The complexity of constraint satisfaction games and QCSP. Inf. Comput. 207(9), 923\u2013944 (2009)","journal-title":"Inf. Comput."},{"key":"19_CR8","doi-asserted-by":"publisher","unstructured":"Bulteau, L., Dabrowski, K.K., K\u00f6hler, N., Ordyniak, S., Paulusma, D.: An algorithmic framework for locally constrained homomorphisms. In: Bekos, M.A., Kaufmann, M. (eds.) Graph-Theoretic Concepts in Computer Science. WG 2022. LNCS, vol. 13453, pp. 114\u2013128. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15914-5_9","DOI":"10.1007\/978-3-031-15914-5_9"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Fiala, J., van\u2019t Hof, P., Paulusma, D., Tesar, M.: Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. Theor. Comput. Sci. 590, 86\u201395 (2015)","DOI":"10.1016\/j.tcs.2015.01.028"},{"key":"19_CR10","unstructured":"Chen, H.: Quantified constraint satisfaction and bounded treewidth. In: De Mantaras, R.L., Saitta, L. (eds.), Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI\u20192004, including Prestigious Applicants of Intelligent Systems, PAIS 2004, Valencia, Spain, 22\u201327 August 2004, pp. 161\u2013165. IOS Press (2004)"},{"issue":"3","key":"19_CR11","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","volume":"38","author":"R Dechter","year":"1989","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artif. Intell. 38(3), 353\u2013366 (1989)","journal-title":"Artif. Intell."},{"issue":"2","key":"19_CR12","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.cosrev.2008.06.001","volume":"2","author":"J Fiala","year":"2008","unstructured":"Fiala, J., Kratochv\u00edl, J.: Locally constrained graph homomorphisms - structure, complexity, and applications. Comput. Sci. Rev. 2(2), 97\u2013111 (2008)","journal-title":"Comput. Sci. Rev."},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Fichte, J.K., Ganian, R., Hecher, M., Slivovsky, F., Ordyniak, S.: Structure-aware lower bounds and broadening the horizon of tractability for QBF. In: LICS, pp. 1\u201314 (2023)","DOI":"10.1109\/LICS56636.2023.10175675"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0012-365X(00)00009-1","volume":"222","author":"A Galluccio","year":"2000","unstructured":"Galluccio, A., Hell, P., Ne\u0161et\u0159il, J.: The complexity of $${H}$$-colouring of bounded degree graphs. Discret. Math. 222, 101\u2013109 (2000)","journal-title":"Discret. Math."},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.dam.2013.10.010","volume":"166","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Paulusma, D.: List coloring in the absence of two subgraphs. Discret. Appl. Math. 166, 123\u2013130 (2014)","journal-title":"Discret. Appl. Math."},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.dam.2014.08.008","volume":"180","author":"PA Golovach","year":"2015","unstructured":"Golovach, P.A., Paulusma, D., Ries, B.: Coloring graphs characterized by a forbidden subgraph. Discret. Appl. Math. 180, 101\u2013110 (2015)","journal-title":"Discret. Appl. Math."},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54, 1:1\u20131:24 (2007)","DOI":"10.1145\/1206035.1206036"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Grzesik, A., Klimo\u0161ov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for Maximum Weight Independent set on $${P}_6$$-free graphs. ACM Trans. Algorithms 18, 4:1\u20134:57 (2022)","DOI":"10.1145\/3414473"},{"key":"19_CR19","unstructured":"Hemaspaandra, E.: Dichotomy theorems for alternation-bounded quantified boolean formulas. CoRR, cs.CC\/0406006 (2004)"},{"key":"19_CR20","unstructured":"Johnson, M., et al.: Complexity framework for forbidden subgraphs I: the framework. CoRR, 2211.12887, 2022"},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.tcs.2012.02.036","volume":"438","author":"M Kami\u0144ski","year":"2012","unstructured":"Kami\u0144ski, M.: Max-cut and containment relations in graphs. Theor. Comput. Sci. 438, 89\u201395 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR22","doi-asserted-by":"publisher","unstructured":"Kinnersley, N.G.: The vertex separation number of a graph equals its path-width. Inf. Process. Lett. 42(6), 345\u2013350 (1992). https:\/\/doi.org\/10.1016\/0020-0190(92)90234-M","DOI":"10.1016\/0020-0190(92)90234-M"},{"key":"19_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-45477-2_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D Kr\u00e1l\u2019","year":"2001","unstructured":"Kr\u00e1l\u2019, D., Kratochv\u00edl, J., Tuza, Z., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 254\u2013262. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45477-2_23"},{"key":"19_CR24","unstructured":"Martin, B.: Logic, computation and constraint satisfaction. PhD thesis, University of Leicester, UK, 2005"},{"key":"19_CR25","unstructured":"Martin, B., Pandey, S., Paulusma, D., Siggers, M., Smith, S., van Leeuwen, E.J.: Complexity framework for forbidden subgraphs II: when hardness is not preserved under edge subdivision (2023). http:\/\/arxiv.org\/abs\/2211.14214arXiv:2211.14214"},{"key":"19_CR26","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity. AC, vol. 28. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4"},{"key":"19_CR27","doi-asserted-by":"publisher","first-page":"2453","DOI":"10.1137\/22M1468864","volume":"36","author":"G Paesani","year":"2022","unstructured":"Paesani, G., Paulusma, D., Rzazewski, P.: Feedback vertex set and even cycle transversal for $${H}$$-free graphs: finding large block graphs. SIAM J. Discret. Math. 36, 2453\u20132472 (2022)","journal-title":"SIAM J. Discret. Math."},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory Ser. B 36, 49\u201364 (1984)","DOI":"10.1016\/0095-8956(84)90013-3"}],"container-title":["Lecture Notes in Computer Science","Twenty Years of Theoretical and Practical Synergies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-64309-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T22:03:19Z","timestamp":1719871399000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-64309-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031643088","9783031643095"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-64309-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"2 July 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","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":"8 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}