{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T15:00:58Z","timestamp":1743001258513,"version":"3.40.3"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319587400"},{"type":"electronic","value":"9783319587417"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-58741-7_26","type":"book-chapter","created":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T12:59:28Z","timestamp":1494507568000},"page":"270-281","source":"Crossref","is-referenced-by-count":1,"title":["Surjective H-Colouring: New Hardness Results"],"prefix":"10.1007","author":[{"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[]},{"given":"Matthew","family":"Johnson","sequence":"additional","affiliation":[]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]},{"given":"Anthony","family":"Stewart","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,12]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","first-page":"1680","DOI":"10.1016\/j.dam.2012.03.029","volume":"160","author":"M Bodirsky","year":"2012","unstructured":"Bodirsky, M., K\u00e1ra, J., Martin, B.: The complexity of surjective homomorphism problems - a survey. Discrete Appl. Math. 160, 1680\u20131690 (2012)","journal-title":"Discrete Appl. Math."},{"key":"26_CR2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/jgt.10073","volume":"42","author":"T Feder","year":"2003","unstructured":"Feder, T., Hell, P., Huang, J.: Bi-arc graphs and the complexity of list homomorphisms. J. Graph Theory 42, 61\u201380 (2003)","journal-title":"J. Graph Theory"},{"key":"26_CR3","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1137\/080738866","volume":"24","author":"T Feder","year":"2010","unstructured":"Feder, T., Hell, P., Jonsson, P., Krokhin, A., Nordh, G.: Retractions to pseudoforests. SIAM J. Discrete Math. 24, 101\u2013112 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"26_CR4","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28, 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"key":"26_CR5","doi-asserted-by":"crossref","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, 97\u2013111 (2008)","journal-title":"Comput. Sci. Rev."},{"key":"26_CR6","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.tcs.2005.09.029","volume":"349","author":"J Fiala","year":"2005","unstructured":"Fiala, J., Paulusma, D.: A complete complexity classification of the role assignment problem. Theoret. Comput. Sci. 349, 67\u201381 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR7","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/s00236-012-0164-0","volume":"49","author":"PA Golovach","year":"2012","unstructured":"Golovach, P.A., Lidick\u00fd, B., Martin, B., Paulusma, D.: Finding vertex-surjective graph homomorphisms. Acta Informatica 49, 381\u2013394 (2012)","journal-title":"Acta Informatica"},{"key":"26_CR8","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.tcs.2012.06.039","volume":"457","author":"PA Golovach","year":"2012","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: Computing vertex-surjective homomorphisms to partially reflexive trees. Theoret. Comput. Sci. 457, 86\u2013100 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR9","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-colouring. J. Comb. Theory Ser. B 48, 92\u2013110 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"26_CR10","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)"},{"key":"26_CR11","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.jctb.2014.09.002","volume":"111","author":"B Martin","year":"2015","unstructured":"Martin, B., Paulusma, D.: The computational complexity of disconnected cut and \n            $$2 K_2$$\n          -partition. J. Comb. Theory Ser. B 111, 17\u201337 (2015)","journal-title":"J. Comb. Theory Ser. B"},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/3-540-45477-2_26","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Patrignani","year":"2001","unstructured":"Patrignani, M., Pizzonia, M.: The complexity of the matching-cut problem. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 284\u2013295. Springer, Heidelberg (2001). doi:\n10.1007\/3-540-45477-2_26"},{"key":"26_CR13","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1137\/S0097539701383522","volume":"32","author":"N Vikas","year":"2002","unstructured":"Vikas, N.: Computational complexity of compaction to reflexive cycles. SIAM J. Comput. 32, 253\u2013280 (2002)","journal-title":"SIAM J. Comput."},{"key":"26_CR14","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1137\/S0097539701397801","volume":"33","author":"N Vikas","year":"2004","unstructured":"Vikas, N.: Compaction, retraction, and constraint satisfaction. SIAM J. Comput. 33, 761\u2013782 (2004)","journal-title":"SIAM J. Comput."},{"key":"26_CR15","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/j.jcss.2004.07.003","volume":"71","author":"N Vikas","year":"2005","unstructured":"Vikas, N.: A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results. J. Comput. Syst. Sci. 71, 406\u2013439 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"26_CR16","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/s00453-012-9720-9","volume":"67","author":"N Vikas","year":"2013","unstructured":"Vikas, N.: Algorithms for partition of some class of graphs under compaction and vertex-compaction. Algorithmica 67, 180\u2013206 (2013)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Unveiling Dynamics and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-58741-7_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,8,31]],"date-time":"2017-08-31T09:03:29Z","timestamp":1504170209000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-58741-7_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319587400","9783319587417"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-58741-7_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}