{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:38Z","timestamp":1777516778001,"version":"3.51.4"},"reference-count":21,"publisher":"SAGE Publications","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["COM"],"published-print":{"date-parts":[[2018,12,19]]},"DOI":"10.3233\/com-180084","type":"journal-article","created":{"date-parts":[[2018,2,16]],"date-time":"2018-02-16T11:03:21Z","timestamp":1518779001000},"page":"27-42","source":"Crossref","is-referenced-by-count":5,"title":["Surjective H-colouring: New hardness results"],"prefix":"10.1177","volume":"8","author":[{"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway. petr.golovach@ii.uib.no"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Johnson","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Durham University, U.K.. matthew.johnson@durham.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Durham University, U.K.. barnaby.d.martin@durham.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Durham University, U.K.. daniel.paulusma@durham.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony","family":"Stewart","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Durham University, U.K.. a.g.stewart@durham.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"key":"10.3233\/COM-180084_ref1","doi-asserted-by":"publisher","first-page":"1680","DOI":"10.1016\/j.dam.2012.03.029","article-title":"The complexity of surjective homomorphism problems\u00a0\u2013 a survey","volume":"160","author":"Bodirsky","year":"2012","journal-title":"Discrete Applied Mathematics"},{"key":"10.3233\/COM-180084_ref2","doi-asserted-by":"crossref","unstructured":"A.A.\u00a0Bulatov, A dichotomy theorem for nonuniform CSPs, in: Proc. FOCS 2017, pp.\u00a0319\u2013330.","DOI":"10.1109\/FOCS.2017.37"},{"key":"10.3233\/COM-180084_ref3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/jgt.10073","article-title":"Bi-arc graphs and the complexity of list homomorphisms","volume":"42","author":"Feder","year":"2003","journal-title":"Journal of Graph Theory"},{"key":"10.3233\/COM-180084_ref4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/080738866","article-title":"Retractions to pseudoforests","volume":"24","author":"Feder","year":"2010","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"10.3233\/COM-180084_ref5","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","article-title":"The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory","volume":"28","author":"Feder","year":"1998","journal-title":"SIAM Journal on Computing"},{"key":"10.3233\/COM-180084_ref6","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.cosrev.2008.06.001","article-title":"Locally constrained graph homomorphisms\u00a0\u2013 structure, complexity, and applications","volume":"2","author":"Fiala","year":"2008","journal-title":"Computer Science Review"},{"key":"10.3233\/COM-180084_ref7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2005.09.029","article-title":"A complete complexity classification of the role assignment problem","volume":"349","author":"Fiala","year":"2005","journal-title":"Theoretical Computer Science"},{"key":"10.3233\/COM-180084_ref8","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/11685654_12","article-title":"On promise problems (a survey)","volume":"3895","author":"Goldreich","year":"2006","journal-title":"Lecture Notes in Computer Science"},{"key":"10.3233\/COM-180084_ref9","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s00236-012-0164-0","article-title":"Finding vertex-surjective graph homomorphisms","volume":"49","author":"Golovach","year":"2012","journal-title":"Acta Informatica"},{"key":"10.3233\/COM-180084_ref10","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2012.06.039","article-title":"Computing vertex-surjective homomorphisms to partially reflexive trees","volume":"457","author":"Golovach","year":"2012","journal-title":"Theoretical Computer Science"},{"key":"10.3233\/COM-180084_ref11","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","article-title":"On the complexity of H-colouring","volume":"48","author":"Hell","year":"1990","journal-title":"Journal of Combinatorial Theory, Series\u00a0B"},{"key":"10.3233\/COM-180084_ref12","doi-asserted-by":"crossref","unstructured":"P.\u00a0Hell and J.\u00a0Ne\u0161et\u0159il, Graphs and Homomorphisms, Oxford University Press, 2004.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"10.3233\/COM-180084_ref13","unstructured":"B.\u00a0Larose, B.\u00a0Martin and D.\u00a0Paulusma, Surjective H-colouring over reflexive digraphs, in: Proc. STACS 2018, 4\u00a0Leibniz International Proceedings in Informatics, Vol.\u00a096, 2018, pp.\u00a049:1\u201349:14."},{"key":"10.3233\/COM-180084_ref14","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.jctb.2014.09.002","article-title":"The computational complexity of disconnected cut and 2 K 2 -partition","volume":"111","author":"Martin","year":"2015","journal-title":"Journal of Combinatorial Theory, Series\u00a0B"},{"key":"10.3233\/COM-180084_ref15","doi-asserted-by":"crossref","unstructured":"M.\u00a0Patrignani and M.\u00a0Pizzonia, The complexity of the matching-cut problem, in: Proc. WG 2001, Lecture Notes in Computer Science, Vol.\u00a02204, 2001, pp.\u00a0284\u2013295.","DOI":"10.1007\/3-540-45477-2_26"},{"key":"10.3233\/COM-180084_ref16","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1137\/S0097539701383522","article-title":"Computational complexity of compaction to reflexive cycles","volume":"32","author":"Vikas","year":"2002","journal-title":"SIAM Journal on Computing"},{"key":"10.3233\/COM-180084_ref17","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1137\/S0097539701397801","article-title":"Compaction, retraction, and constraint satisfaction","volume":"33","author":"Vikas","year":"2004","journal-title":"SIAM Journal on Computing"},{"key":"10.3233\/COM-180084_ref18","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/j.jcss.2004.07.003","article-title":"A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results","volume":"71","author":"Vikas","year":"2005","journal-title":"Journal of Computer and System Sciences"},{"key":"10.3233\/COM-180084_ref19","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/s00453-012-9720-9","article-title":"Algorithms for partition of some class of graphs under compaction and vertex-compaction","volume":"67","author":"Vikas","year":"2013","journal-title":"Algorithmica"},{"key":"10.3233\/COM-180084_ref20","unstructured":"N.\u00a0Vikas, Computational complexity of graph partition under vertex-compaction to an irreflexive hexagon, in: Proc. MFCS 2017, Leibniz International Proceedings in Informatics, Vol.\u00a083, 2017, pp.\u00a069:1\u201369:14."},{"key":"10.3233\/COM-180084_ref21","doi-asserted-by":"crossref","unstructured":"D.\u00a0Zhuk, A proof of CSP dichotomy conjecture, in: FOCS 2017, pp.\u00a0331\u2013342.","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["Computability"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/COM-180084","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:59Z","timestamp":1777391999000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-180084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,19]]},"references-count":21,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.3233\/com-180084","relation":{},"ISSN":["2211-3576","2211-3568"],"issn-type":[{"value":"2211-3576","type":"electronic"},{"value":"2211-3568","type":"print"}],"subject":[],"published":{"date-parts":[[2018,12,19]]}}}