{"entities":{"Q1764813":{"pageid":1775555,"ns":120,"title":"Item:Q1764813","lastrevid":48418801,"modified":"2026-01-04T16:24:35Z","type":"item","id":"Q1764813","labels":{"en":{"language":"en","value":"The restrictive \\(H\\)-coloring problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2136949"}},"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":"Q1764813$F494418E-7FEA-4834-B58F-7779FB77FACF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dd8cd6b0d8abe815b1fa7f09a5f0594dd246d109","datavalue":{"value":{"text":"The restrictive \\(H\\)-coloring problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1764813$0D0A2666-B051-4909-8D66-ABAF257E3CAC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"425bb3620ba1d7dba8dd8ebdeab2b6c640f9559f","datavalue":{"value":"1062.05055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764813$170BEE92-9B6E-4DB1-9FF3-8A97B1F4D4F5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1348fb004fb071dffe1335a9785ae0b754bd6be2","datavalue":{"value":{"entity-type":"item","numeric-id":284716,"id":"Q284716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$CF297C11-AFB0-407E-A0EA-5B0E46284DF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2dca00cf5e3506d17c2986004891f80ecd82aa0","datavalue":{"value":{"entity-type":"item","numeric-id":314817,"id":"Q314817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$972E818C-E258-4EC7-AB04-82E600BD2096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4bd572a0b0f71443497a4605c8e572a1dc2df55","datavalue":{"value":{"entity-type":"item","numeric-id":1391311,"id":"Q1391311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$2C899FC4-9A14-4FE9-9742-B7832A7C52B2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$E176B5E4-7ED4-49A9-B4D3-618318B8A5F4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e6fd9f57da46494686492c936ca92ef875382ca4","datavalue":{"value":{"time":"+2005-02-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1764813$67B3EA86-1861-4183-98E8-F41F3F2C2B7F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6a35581687d7e356b0c76c86509d187a917f8d74","datavalue":{"value":"Given two graphs \\(G\\) and \\(H\\) without multiple edges, an \\(H\\)-coloring of \\(G\\) is a homomorphism from \\(G\\) to \\(H\\) mapping the vertices in \\(G\\) to vertices in \\(H\\) in such a way that the image of an edge is also an edge. The \\(H\\)-coloring problem asks for the existence of an \\(H\\)-coloring while the counting \\(H\\)-coloring problem asks for the number of \\(H\\)-colorings of \\(G\\) (see the papers of \\textit{P. Hell} and \\textit{J. Ne\u0161et\u0159il} [J. Comb. Theory, Ser. B 48, 92--110 (1990; Zbl 0639.05023)] and of \\textit{M. Dyer} and \\textit{C. Greenhill} [Random Struct. Algorithms 17, 260--289 (2000; Zbl 0965.68073)]).   In this paper, restrictive variants of these problems are studied where the number of preimages of certain vertices is predetermined. The computational complexity of these problems is investigated. The authors show that their results apply also for the list versions and other extensions of the problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764813$2766B6CB-B925-4685-80F1-D2760DF86C64","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"28b1fb367b3a6335e647ddbd540f63d134723dd1","datavalue":{"value":{"entity-type":"item","numeric-id":222481,"id":"Q222481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$1D15886C-D57D-4222-AFCA-540CE3BDF54C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764813$C7DDDD1F-D8BD-4281-9290-6659B682B1DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764813$7CCF1EC5-F0C6-42CB-A6B8-93304053150E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764813$A311BCB6-EE2E-4BD7-9600-F30E98B0B400","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a89a76e8ae4ee8f7034fda09f45201a6d8a25f39","datavalue":{"value":"2136949","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764813$E7365482-0F95-40EF-BA77-71DB58349C80","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff1afee326827a19ca90095460fac35ed2a55d6d","datavalue":{"value":"restrictive \\(H\\)-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764813$1D27017C-3EA8-4A22-A57D-95DDBDF6C918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58712acbde860c0153062a2693545d5f45b74754","datavalue":{"value":"graph homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764813$BAD05C04-EED8-4AD3-86AD-2E43DC8EA7C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764813$8F8CDDBF-0C4A-4346-B32A-F9E5E079C073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764813$CACAF2DD-47E5-4E59-8F8C-B069133BC72C","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":"Q1764813$202307F2-BCC1-4ACE-AE84-B9E3D9BC8DBE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"480b90ab4a8403cb0a5d3beb4598ad44388da083","datavalue":{"value":"https://doi.org/10.1016/j.dam.2004.01.018","type":"string"},"datatype":"url"},"type":"statement","id":"Q1764813$C95D57E7-6F75-4011-A9D1-2AA8E265645A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5edbe952bcdf3d73b615d7bfcc0d1ec9272b4ee1","datavalue":{"value":"W1986011439","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764813$CAF33488-CA80-4FEC-AFD4-85C851119848","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"975b7052851d48061120ca868021b20727c573a0","datavalue":{"value":{"entity-type":"item","numeric-id":1198051,"id":"Q1198051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$C404B42B-EA4B-40AA-B9DD-752B57355627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"513b3b45467d31a2a9e4ce3e34f9984abdc367e8","datavalue":{"value":{"entity-type":"item","numeric-id":4779153,"id":"Q4779153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$BB98848B-7DA4-4969-89F8-CBF0D4411F09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df2053dd94a310b06516340e3eba4a9040435e95","datavalue":{"value":{"entity-type":"item","numeric-id":4660720,"id":"Q4660720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$55B8EC63-09C5-47B0-8DE8-C7A12797F015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1a96aac0e5ae27d313107c757367cc55dc30913","datavalue":{"value":{"entity-type":"item","numeric-id":4521549,"id":"Q4521549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$F8DE91B1-CBEF-4246-B2BB-DC8ABEBF44DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75d4076d4897ab3cc8f6948af493950051b74467","datavalue":{"value":{"entity-type":"item","numeric-id":1127870,"id":"Q1127870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$430A9E4F-53D2-4CF1-9456-4155D28BBBEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72636d83503e896e571d6f2c09be11cb7bc2ca51","datavalue":{"value":{"entity-type":"item","numeric-id":1977431,"id":"Q1977431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$F9567311-E118-4432-BE26-36680C7B354E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2cad0419316111f4f87da733ecde246b034fc01","datavalue":{"value":{"entity-type":"item","numeric-id":4798127,"id":"Q4798127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$2B041BAF-34EA-4D8D-B2C5-0ABCF644C8E9","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":"Q1764813$A7FC7C16-8C7F-4A21-A0B2-194B23BB92EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec165abc7ade014841f417bcba31a647c17e0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$18FFB0DD-B2FF-42D4-AD75-D260004AB0F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91877bdee03e7e9615697f3e0bdd6854142d5348","datavalue":{"value":{"entity-type":"item","numeric-id":4660723,"id":"Q4660723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764813$6E17D351-0C0E-4A0E-8030-14A8CE062069","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"79e8592c13875c0f087fe70eeba083a3f78a383a","datavalue":{"value":"10.1016/J.DAM.2004.01.018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764813$AEBEA881-16CD-433F-A223-7D65187C8BA2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b164218765f44b5ac28050552e320a4ecd77dde","datavalue":{"value":{"entity-type":"item","numeric-id":4414491,"id":"Q4414491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f39cc1e5c8b7a242b7dc9687a22ed6d26441d48","datavalue":{"value":{"amount":"+0.9284197688102722","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":"Q1764813$3009F680-B21A-4BA5-A251-3544BA699545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5294193571806a3ee60a9d0dd043450fcbba6f83","datavalue":{"value":{"entity-type":"item","numeric-id":2370448,"id":"Q2370448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beb3f21e8844d05f16358250bf36bb35a61c9a1d","datavalue":{"value":{"amount":"+0.8776793479919434","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":"Q1764813$348CAD5D-9421-4BB9-A85A-4BC9D9EF2845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eae112f0ba3fdc666a9d9f466bf913083758c944","datavalue":{"value":{"entity-type":"item","numeric-id":4668721,"id":"Q4668721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fca5fb50110f36351756d011ec04784ba4301e40","datavalue":{"value":{"amount":"+0.8743945956230164","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":"Q1764813$ACE566C4-84F8-435F-8CBB-7CDCF338F5CB","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":"9011d63e3c7ff4b91ffffe2c82bff1a288c5e48e","datavalue":{"value":{"amount":"+0.8465271592140198","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":"Q1764813$5CD9F70B-A5AB-4F9A-9569-897F95C0EFE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f59c14f441149b5541627744cb1128897f90b36b","datavalue":{"value":{"entity-type":"item","numeric-id":4660723,"id":"Q4660723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"868e99d16e4aa79cacf7ceb2030c5b08ae992609","datavalue":{"value":{"amount":"+0.8402963280677795","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":"Q1764813$A5A14601-F097-44A5-A604-1183B3FEB607","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1764813","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1764813"}}}}}