{"entities":{"Q1183461":{"pageid":1194210,"ns":120,"title":"Item:Q1183461","lastrevid":66785550,"modified":"2026-04-12T12:50:53Z","type":"item","id":"Q1183461","labels":{"en":{"language":"en","value":"A note on restricted \\(H\\)-colouring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33306"}},"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":"Q1183461$3567B889-44A5-4A40-A2A3-D655FCE50F0C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3556b911fb5c9b88710946293e19ee826356c71a","datavalue":{"value":{"text":"A note on restricted \\(H\\)-colouring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183461$1E588ACA-CA8D-4566-8764-7B7034095F6E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8557d24a739a1403096f4cc2e76b8a2cb640ceaf","datavalue":{"value":"0761.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183461$9006280E-7AC4-4152-A688-926F2D6248BA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9439b737db14b5bc1f720f76e1342ffed3cad63c","datavalue":{"value":"10.1016/0020-0190(91)90171-D","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183461$06F23A46-4FB0-4F9A-8F9E-FF3608495599","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183461$09EC8207-1CEA-4CCD-B37D-E12CF2DEF13D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183461$C08B55F5-8D08-433F-8A19-8345769A365C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"78501f1a2d22e5f251607a2f112e658a41791195","datavalue":{"value":"Let \\(H\\) be a graph whose vertices are called colors. An \\(H\\)-coloring of a graph \\(G\\) is a function \\(f:V(G)\\to V(H)\\) such that \\((f(u),f(v))\\) is an edge of \\(H\\) whenever \\((u,v)\\) is an edge in \\(G\\). The authors consider the complexity of the following problem: ``Given a \\(k\\)-chromatic graph \\(G\\) and a \\(k\\)-coloring of its vertices; does there exist an \\(H\\)-coloring of \\(G\\)?'' They prove that if \\(H\\) is loopless and the clique number \\(\\omega(H)\\) is less than \\(k\\leq\\chi(H)\\), then the problem is NP-hard. Otherwise it is polynomially solvable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183461$EA1597F0-E285-428F-B7C7-D0900B13A67B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183461$D17CD67D-9E42-4DD8-AE14-08F4A851339E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183461$90934153-B342-4327-BDF1-C07687F21B79","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c26579361b6e1d64f2e31859b578e9deb534af77","datavalue":{"value":"33306","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183461$B0DF9744-E5FA-4741-ACCB-FAB63764F535","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183461$9FEA6E7B-1061-46D2-AD96-C2D8C4B91969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183461$63C94968-28A2-41F4-A4FA-DD3F22FC3D80","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"52bb6023fc2fb290bed8e39de5ac83994a0dee8f","datavalue":{"value":{"entity-type":"item","numeric-id":301585,"id":"Q301585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183461$B5CE632E-285D-43D3-92E1-29072F2169AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"57555e49e581043524b19e8ff224491cb25ceec4","datavalue":{"value":{"entity-type":"item","numeric-id":189757,"id":"Q189757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183461$AD9B029C-C81B-419A-BD3A-4A774A046487","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183461$AAC75339-BC48-4727-8D34-A6A5AB74A545","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":"Q1183461$17CBEC9F-6EB3-4CDB-A705-3EAB3089D69A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4d98b1ff8a95acec1e12dac2f68feea66460460","datavalue":{"value":{"entity-type":"item","numeric-id":3348926,"id":"Q3348926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183461$ACBCCA2B-6179-4C16-868F-F3DE9AAF0BBF","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":"Q1183461$559716A6-CE36-4812-89E8-EDDBB05CC9DE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9841da466af1730fffaa24ac1775a239ac92b973","datavalue":{"value":"https://doi.org/10.1016/0020-0190(91)90171-d","type":"string"},"datatype":"url"},"type":"statement","id":"Q1183461$AFF8F147-35F3-4A2B-AA6E-02026C0DBDA4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7c6c357886c89819d5db57bdcf55ecbadf98a897","datavalue":{"value":"W2038944411","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183461$9C4D06DD-19B1-4E03-A610-155EDD7C0799","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":"ce1edf34b185c5ff76f498ef3ea70a9cd57d7479","datavalue":{"value":{"amount":"+0.861832320690155","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":"Q1183461$26BE1A74-A115-43FD-AC8B-775A5AA96DDE","rank":"normal"},{"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":"913129ae70ec651dec66bd11940daf880a15c7cd","datavalue":{"value":{"amount":"+0.8607360124588013","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":"Q1183461$D7DD1926-2A99-4430-A4EF-113721FAAE45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aae131b8b2ba59cb8f9fe6f97ab17a8d0c89046e","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"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":"Q1183461$8B04ED60-9D8D-4330-9E42-9D203D0A2707","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":"8c85a3c96e18f0794b7321f870f7ab0b21d29371","datavalue":{"value":{"amount":"+0.8557373881340027","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":"Q1183461$26878867-D556-4CF1-85E6-A6ACF58A895E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40eea57eb116ad49129f868e1ee17276c4a6810b","datavalue":{"value":{"entity-type":"item","numeric-id":1842146,"id":"Q1842146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c85a3c96e18f0794b7321f870f7ab0b21d29371","datavalue":{"value":{"amount":"+0.8557373881340027","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":"Q1183461$71580DD0-CEB4-4C97-9DA0-324A8AD0B113","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on restricted \\(H\\)-colouring","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_restricted_%5C(H%5C)-colouring"}}}}}