{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:46:50Z","timestamp":1725544010673},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540341666"},{"type":"electronic","value":"9783540341680"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11753728_18","type":"book-chapter","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T16:17:13Z","timestamp":1146154633000},"page":"159-170","source":"Crossref","is-referenced-by-count":2,"title":["Bounded-Degree Forbidden Patterns Problems Are Constraint Satisfaction Problems"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Dantchev","sequence":"first","affiliation":[]},{"given":"Florent","family":"Madelaine","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","unstructured":"Madelaine, F., Stewart, I.A.: Constraint satisfaction, logic and forbidden patterns (submitted, 2005)"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","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.\u00a028, 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"key":"18_CR3","doi-asserted-by":"publisher","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":"18_CR4","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jctb.2000.1970","volume":"80","author":"J. Ne\u0161et\u0159il","year":"2000","unstructured":"Ne\u0161et\u0159il, J., Tardif, C.: Duality theorems for finite structures (characterising gaps and good characterisations). Journal of Combin. Theory Ser. B\u00a080, 80\u201397 (2000)","journal-title":"Journal of Combin. Theory Ser. B"},{"key":"18_CR5","unstructured":"Madelaine, F., Stewart, I.A.: Some problems not definable using structures homomorphisms. Ars Combinatoria\u00a0LXVII (2003)"},{"key":"18_CR6","unstructured":"Bordisky, M.: Constraint Satisfaction with Infinite Domains. PhD thesis, Humboldt-Universit\u00e4t zu Berlin (2004)"},{"key":"18_CR7","unstructured":"Madelaine, F.: Constraint satisfaction problems and related logic. PhD thesis, University of Leicester, Department of Mathematics and Computer Science (2003)"},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1006\/eujc.1993.1004","volume":"14","author":"R. H\u00e4ggkvist","year":"1993","unstructured":"H\u00e4ggkvist, R., Hell, P.: Universality of A-mote graphs. European Journal of Combinatorics\u00a014, 23\u201327 (1993)","journal-title":"European Journal of Combinatorics"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0012-365X(00)00009-1","volume":"222","author":"P. Hell","year":"2000","unstructured":"Hell, P., Galluccio, A., Ne\u0161et\u0159il, J.: The complexity of H-coloring bounded degree graphs. Discrete Mathematics\u00a0222, 101\u2013109 (2000)","journal-title":"Discrete Mathematics"},{"issue":"1-3","key":"18_CR10","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0012-365X(01)00421-6","volume":"250","author":"P.A. Dreyer Jr.","year":"2002","unstructured":"Dreyer Jr., P.A., Malon, C., Ne\u0161et\u0159il, J.: Universal H-colourable graphs without a given configuration. Discrete Mathematics\u00a0250(1-3), 245\u2013252 (2002)","journal-title":"Discrete Mathematics"},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0166-218X(94)90019-1","volume":"54","author":"B. Courcelle","year":"1994","unstructured":"Courcelle, B.: The monadic second order logic of graphs VI: On several representations of graphs by relational structures. Discrete Applied Mathematics\u00a054, 117\u2013149 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0012-365X(97)84217-3","volume":"165-166","author":"D. Achlioptas","year":"1997","unstructured":"Achlioptas, D.: The complexity of G-free colourability. Discrete Mathematics\u00a0165-166, 21\u201330 (1997)","journal-title":"Discrete Mathematics"},{"key":"18_CR13","volume-title":"Computers and intractability: a guide to NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and intractability: a guide to NP-completeness. Freeman, San Francisco (1979)"},{"key":"18_CR14","unstructured":"Madelaine, F., Dantchev, S.: Online appendix of this paper (2006), Electronic form available from: \n                    \n                      www.dur.ac.uk\/f.r.madelaine"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11753728_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:03:31Z","timestamp":1619492611000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11753728_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540341666","9783540341680"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11753728_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}