{"entities":{"Q1183345":{"pageid":1194094,"ns":120,"title":"Item:Q1183345","lastrevid":66442230,"modified":"2026-04-12T10:06:08Z","type":"item","id":"Q1183345","labels":{"en":{"language":"en","value":"Polynomial graph-colorings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33086"}},"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":"Q1183345$C3B41CC0-1F93-4006-B96F-D2639C20F8AA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"648e0e21f2609b88bff54b4ad68aecc1be41232b","datavalue":{"value":{"text":"Polynomial graph-colorings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183345$4A9BCCC5-BC01-4059-986D-C117F5E1A154","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"30dbe97937988b06253ee91e9f4ceb4f6b003c4b","datavalue":{"value":"0761.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183345$8CB2782E-98BF-4F27-8B7F-42C049F6091D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a85c7ea9802d4931952b1d4591d7f96104388c1c","datavalue":{"value":"10.1016/0166-218X(92)90294-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183345$08673105-E07F-4014-AD90-01C844461A51","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a67dac26dd2ec0008e83edc4de86c86c49064c7a","datavalue":{"value":{"entity-type":"item","numeric-id":1183344,"id":"Q1183344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183345$EBAECE82-D636-4B0E-9001-A56350696C43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebde143434d63bb91413660f73ab09b4563fd56f","datavalue":{"value":{"entity-type":"item","numeric-id":1262764,"id":"Q1262764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183345$DD5FA079-EA37-4F46-8BB0-2CEC10F10EE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a99c5b7728e1965ef01019ed8fae6583a2f22e4","datavalue":{"value":{"entity-type":"item","numeric-id":170010,"id":"Q170010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183345$85929B45-596A-4FC5-B411-B8FF71C88323","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":"Q1183345$1ACB55DE-9299-4E53-959D-975F12F0583C","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":"Q1183345$0C439BF3-FD13-4EEF-9982-B1B1966551C8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c09caa1315b66dfd3a8debe460b89cddaa46db95","datavalue":{"value":"For directed graphs \\(G=(V_ G,E_ G)\\) and \\(H=(V_ H,E_ H)\\) an \\(H\\)- coloring of \\(G\\) is a mapping \\(f:V_ G\\to V_ H\\) such that for all edges \\((u,v)\\in E_ G\\) we have \\((f(u),f(v))\\in E_ H\\). The authors introduce a new technique for proving that the \\(H\\)-coloring problem is polynomially solvable for some fixed digraphs \\(H\\). Among others, there are semipaths (paths with edges directed in either direction), a fact which was not previously known. The result for semipaths is ``strong'' in the sense that there exists a tree \\(T\\) (also shown by the authors) for which the \\(T\\)-coloring problem is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183345$5252414C-572B-44A2-B06C-897B60774FA9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183345$E81BA34C-D721-460C-A559-549EE9C229AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183345$4D6F64ED-FE0E-46B1-858F-1CE6FC932ED2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183345$CD8C2021-4654-420D-8855-825F9443135D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183345$04A8C905-41B3-4CA6-AC08-4B198CA4D340","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dc0a17d020c7b6af2b740f2e06541c18876835a5","datavalue":{"value":"33086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183345$00667645-D93A-48BF-A4BE-56CBA5EADE26","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71d82ff8c88b007cc38fea88dca6286ff27f219f","datavalue":{"value":"graph-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183345$032E58EC-FB7C-43EB-90C1-20FABBF86047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183345$BDD68EF0-7DC8-4BC7-84F4-716DA41434E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58712acbde860c0153062a2693545d5f45b74754","datavalue":{"value":"graph homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183345$2C240BA9-43AF-432C-A7BC-6F331A0DFB27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffa219ea2cff89df5162edb57bd2a31ea73e1a26","datavalue":{"value":"digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183345$E9841075-0C65-4804-AE64-467F339DE203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b0ec9ffb190a2616c6e52a8cae445f8e9191ab0","datavalue":{"value":"semipaths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183345$7E380743-0BB0-4E58-8464-F2188DC4BC38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183345$2E4C29D2-D3DC-499D-92EA-D33006997234","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":"Q1183345$4491753F-3C3B-4F5C-98D0-8050C1651DC1","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":"Q1183345$34B4A1C1-B1E2-479D-A2AE-FBA87DC17489","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"206b99faa6ef94198712fcaf2f486a25d7324c8c","datavalue":{"value":"Q54309664","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183345$794B474B-CCD1-4F8F-848D-84F14A304D1B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ca92c5e9c033964322f96db99eac2d4a15c7ec0","datavalue":{"value":{"entity-type":"item","numeric-id":3834066,"id":"Q3834066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183345$631AA660-7C66-4CDD-8FB7-2742918DB7BB","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":"Q1183345$9FCF951B-B2D1-4C27-A58C-7CDC0416587A","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":"Q1183345$CA825533-CA71-4905-8625-A9253A53367E","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":"Q1183345$F336BAC7-1355-4B7B-9A73-5F3FD4F797F7","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":"Q1183345$41CB0A5C-2F98-4942-B92B-F721D097E923","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":"Q1183345$8C33FCDC-F8CE-4A53-8452-93CDBB1AE4E3","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":"Q1183345$3D16BB98-D3ED-4433-A302-A1CE08ED7A4B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08b1c266597f6b8406740427af2f74f9d6662f06","datavalue":{"value":{"entity-type":"item","numeric-id":5096147,"id":"Q5096147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"425c4d8a5d5fc65e8cf72dfdf7a540b17e54a227","datavalue":{"value":{"amount":"+0.940760612487793","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":"Q1183345$2CE06128-E785-4D15-8230-8D15A42887F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38773e3d51d65506ff3b07036d5403578a6749be","datavalue":{"value":{"entity-type":"item","numeric-id":3834066,"id":"Q3834066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a27c81094926dc37379453226147c17aeaec475","datavalue":{"value":{"amount":"+0.8730425834655762","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":"Q1183345$9EE9BDD6-4C63-4833-B5BC-6CFD60CD0DD6","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":"0d2de7bb408966147ce880b10ba29f6221492a9c","datavalue":{"value":{"amount":"+0.8166467547416687","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":"Q1183345$BCAC5C7E-8AE3-42CB-9D81-8AE5E7309815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cbdd1bead25b630c2d47d1edc692caf2800960b","datavalue":{"value":{"entity-type":"item","numeric-id":4873684,"id":"Q4873684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"383a4d4686b60fda86942ae237b80db613a879b7","datavalue":{"value":{"amount":"+0.8158800005912781","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":"Q1183345$1FFFB97F-5668-47F8-ADC5-19C31179A340","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomial graph-colorings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polynomial_graph-colorings"}}}}}