{"entities":{"Q1100215":{"pageid":1110967,"ns":120,"title":"Item:Q1100215","lastrevid":66683511,"modified":"2026-04-12T11:54:58Z","type":"item","id":"Q1100215","labels":{"en":{"language":"en","value":"On the complexity of H-coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4041945"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$589742B8-855E-4C5A-88F2-8447D0BF80B2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ceaaf655ea008dd49046a189dc0b6e9fa27c2a52","datavalue":{"value":{"text":"On the complexity of H-coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1100215$7BA77119-F431-4BF2-8CCE-D96CEB4C2356","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"01af46e6a33c4c260e26157934292cc815501edd","datavalue":{"value":"0639.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100215$699769F8-0E73-4E27-88F3-2E78BA1D1882","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a638d3a0e1010fc2e889f033bc14918e5f224991","datavalue":{"value":"10.1016/0095-8956(90)90132-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100215$C0C04B34-3037-4C5A-BEA4-4ECE18B75C03","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3b5375d01a59455d415f2afee9796bf93e2b3c4","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$823840B5-6DF3-4391-8684-65099EB8799F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380c4124a5ef272e2152da1b5d415130e3e64f8","datavalue":{"value":{"entity-type":"item","numeric-id":175596,"id":"Q175596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$1F6F0E64-3EF7-481D-B8D7-C87B631F6675","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$19DA6A05-9AEA-45D0-89C0-4EC3B6EAB24B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1100215$BFE37B34-9D72-46AC-A46C-7A7FC0A52741","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e8c5331309b04a3f5b2e469ece1f2adbcf933d70","datavalue":{"value":"In standard graph colouring adjacent vertices are required to have different colours. If the set of colours itself forms a graph H, then in an H-colouring of G adjacent vertices are required to have adjacent colours. (Thus an H-colouring of G is just a homomorphism of G to H.) The complexity of deciding the H-colourability of an input graph depends on H. For instances, when H is a complete graph with at least three vertices then H-colourability is NP-complete because it is the traditional colourability problem. When H is bipartite, then H-colourability is equivalent to bipartiteness, and so can be decided in polynomial time.    The authors prove that H-colourability is NP-complete in all other cases. That this was the case was a conjecture of Maurer, Sudborough, and Welzl, popularized in one of David Johnson's NP-completeness columns. It is often not difficult to prove the NP-completeness of H-colouring for particular classes of graphs H, and several such results exist in the literature. The proof of the full conjecture given here is interesting because of the intricate interplay of the various basic reductions and the complex graphs that are employed in them.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100215$6479E4BC-5CC1-40BB-AB36-F902F1E8B4E7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cc7e193006699e29b5b5a77a1be6eeba002bc504","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$C95874A3-4229-4637-A131-17A3DADEB089","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100215$11F5F6B8-81BF-4C9D-BAB9-56192FDD26ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100215$2A9372EA-4584-42D8-9149-B47AFFD99D93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100215$7CCD3CFF-0C00-4827-A5A7-D4E7AA7CA16C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5e300f33e61cf47466aed3df643b655fc992a77","datavalue":{"value":"4041945","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100215$36D4A95F-1757-431F-BC38-6CCA016BEA6C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58712acbde860c0153062a2693545d5f45b74754","datavalue":{"value":"graph homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100215$A9A48865-DACE-42A7-A43C-31F8AE5A8E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100215$3E3CB23C-E3D4-4FAB-81A8-9CE99FDBF987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100215$1CA91B64-4476-4EEF-8F25-826D71F2DFD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c744106c571113b1ad726e1391d2a27478f2fd53","datavalue":{"value":"H-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100215$3DE469A4-DBCC-4582-8E10-7F2A787A9B04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100215$55C5A320-D640-4365-931F-8E7B02CE073B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$78ED1552-8069-4F72-B231-A5287687AF95","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"32c0774067ff2755a854565bb8bc87c538e468dd","datavalue":{"value":"Q56389113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100215$1A1D18AB-A9C6-46BD-9B18-D185F2577502","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"24503c715080e90c80139adbb12057695f60fcf9","datavalue":{"value":{"entity-type":"item","numeric-id":3758851,"id":"Q3758851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$F62CE8FB-9008-4956-8A76-5D6330D7522E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a253dfedc634c3617fd93c34bc6b364162d4ecb1","datavalue":{"value":{"entity-type":"item","numeric-id":3791169,"id":"Q3791169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$691A51BB-F44D-4318-950B-F6E3B9C51F6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0aa46b36cc2e5600de673c133daf504a500dc4ba","datavalue":{"value":{"entity-type":"item","numeric-id":1158767,"id":"Q1158767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$B98E72E7-B85B-4224-8103-25A9B459B6E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc4f0630ec86e5a0d3e96a9ce7ec4c2915d07620","datavalue":{"value":{"entity-type":"item","numeric-id":4083458,"id":"Q4083458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$08C2A590-EA8B-4AF7-A65A-3E1E56000B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a0a8e4ccae21ea52906e2c227811922501b04ce","datavalue":{"value":{"entity-type":"item","numeric-id":4110937,"id":"Q4110937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$ED6509EF-CE73-4201-A6B4-61222BCB9905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$CAA6410E-E9EB-47F5-8A82-E895CE714521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5028065ceb61d7fbbcc8d74c873e6a965e0cc43f","datavalue":{"value":{"entity-type":"item","numeric-id":1110530,"id":"Q1110530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$4F436517-2E4F-4D16-9BA0-BDBFC77CD82B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6a9851ee4b7b8d3be48f0a53f70c8a484520ac6","datavalue":{"value":{"entity-type":"item","numeric-id":2522272,"id":"Q2522272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$80FF9FCA-A756-45C2-940F-D4CC5B08CA11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a1286883a567232f05a87f2260b469736b86a7b","datavalue":{"value":{"entity-type":"item","numeric-id":2562866,"id":"Q2562866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$DDC2C62C-031D-4346-99A2-27FA0FC98C3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3708e7f1e286d66b8df0d583f3854548b62262f","datavalue":{"value":{"entity-type":"item","numeric-id":3874251,"id":"Q3874251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$0FF94633-E2E4-49C5-95DB-C6FA7EDDD21A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ffa47161e66adf933c086be929106e79b917fe5","datavalue":{"value":{"entity-type":"item","numeric-id":1835680,"id":"Q1835680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$581ACC6F-DCEF-4632-B399-31DD83E70BCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d4ff0ae86125fc073ba1153e5f029193cd4ff2","datavalue":{"value":{"entity-type":"item","numeric-id":4065570,"id":"Q4065570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$8EE02BF3-49AD-4AC2-A43E-4000EF01C66C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"842b1f582c7be954c64d94d41d773a79c4d9a96e","datavalue":{"value":{"entity-type":"item","numeric-id":5905223,"id":"Q5905223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$CF9BA5F5-022B-4EF3-B86E-FD6FAB8A1B5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9aa445d6582c3d63ac86f5d12027e0537ae8d21","datavalue":{"value":{"entity-type":"item","numeric-id":3686735,"id":"Q3686735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$C9D6DB7B-16B0-4B47-AB15-558C15DE581C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32669c9303b6fcfce30a867e0ec9585dd818044e","datavalue":{"value":{"entity-type":"item","numeric-id":3878752,"id":"Q3878752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$6B6DEC3F-DE47-4272-A39C-520AFD3EC5E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c26050d258b183673b275b45306c6038c52bc7a3","datavalue":{"value":{"entity-type":"item","numeric-id":1155066,"id":"Q1155066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$62F16FB7-9A90-4539-A70F-4946F97FDB5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8002546a42d967ab22805fe7698fd4d1aa8f6401","datavalue":{"value":{"entity-type":"item","numeric-id":3968465,"id":"Q3968465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$E8473B27-5BE8-422D-8B91-03EB3A23DE6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5debb489774c07261874c925d231c3f3afdf8766","datavalue":{"value":{"entity-type":"item","numeric-id":3912037,"id":"Q3912037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$D7B968AD-C1E9-4466-AA10-4551F6E90822","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01874425d018f2c41712bb3fb8e538c43c3a3a01","datavalue":{"value":{"entity-type":"item","numeric-id":1250117,"id":"Q1250117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$D26AE2C4-8738-48EF-BC9F-BD7E8038C193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da8aaede631bfdc54d481cb5dea09d28a4412b7","datavalue":{"value":{"entity-type":"item","numeric-id":3763600,"id":"Q3763600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100215$5D082BCB-EC92-44EA-8850-FB79009D117C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ff8978cc4d34160e184add4c64934b82f8c91367","datavalue":{"value":"https://doi.org/10.1016/0095-8956(90)90132-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q1100215$C346BCEF-9601-4260-8DBE-071D34921D51","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7147d4cb784c762ec4e7e74e6dda65d4087c7787","datavalue":{"value":"W2077575555","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100215$761504B6-91CE-4DB2-A5ED-7405ED9CFBC2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d80436a7f2f690412ffc3c00684c219eb54ee6e","datavalue":{"value":{"entity-type":"item","numeric-id":3758852,"id":"Q3758852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7be05be4191ec58c1143deb3b701bc4c665fd1d3","datavalue":{"value":{"amount":"+0.9365676641464232","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1100215$C709944E-68C2-4E48-8F13-9DE3C1115D36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10ab42bdb47797eb42b5d4ae7f3f67dc7dea8aed","datavalue":{"value":{"entity-type":"item","numeric-id":3826579,"id":"Q3826579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"005ed91aa1937ee80b1c4a76fc4909bc099e8924","datavalue":{"value":{"amount":"+0.876490592956543","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1100215$736422CB-8724-4DF9-963A-8257CD53C57A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54b3b5dc2d2a84f3f67044bfc541497975254f94","datavalue":{"value":{"entity-type":"item","numeric-id":1183461,"id":"Q1183461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1db8b0e224efe3d732a6f35061d08f0dda90ce38","datavalue":{"value":{"amount":"+0.8574291467666626","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1100215$8960B477-6448-4D8F-BF70-A62D6700F5FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"068de292421424c3d0dbafa52cc761b8d5bd08d9","datavalue":{"value":{"entity-type":"item","numeric-id":1579552,"id":"Q1579552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d520c8c862a3900e035c6716525899c5a8ac7eb6","datavalue":{"value":{"amount":"+0.8544577360153198","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1100215$CB4D19F6-F137-4FF9-9F6D-5C854A8228F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd0e3843b600990de3a46824528772dbf1995a46","datavalue":{"value":{"entity-type":"item","numeric-id":3987041,"id":"Q3987041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d520c8c862a3900e035c6716525899c5a8ac7eb6","datavalue":{"value":{"amount":"+0.8544577360153198","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1100215$0991C469-C2B4-4742-8051-60BD6B88FAD3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of H-coloring","badges":[]}}}}}