{"entities":{"Q6121107":{"pageid":13255414,"ns":120,"title":"Item:Q6121107","lastrevid":58700799,"modified":"2026-04-06T09:31:05Z","type":"item","id":"Q6121107","labels":{"en":{"language":"en","value":"Approximating the chromatic polynomial is as hard as computing it exactly"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7809280"}},"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":"Q6121107$EE9D87E8-85A3-45EC-838D-AFFFE0E41BCF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b498bb43ec5e8fefb583ceb2866139044af911bf","datavalue":{"value":{"text":"Approximating the chromatic polynomial is as hard as computing it exactly","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6121107$AA9328C0-200F-4F55-A04E-81B5F94F4CA9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"90d10f5cc26f5121c81314d601f99497fa584f47","datavalue":{"value":{"entity-type":"item","numeric-id":824264,"id":"Q824264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$E64EB547-539F-4F4B-8A63-669D86BAE9D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a58b411128dfa955d8b29979a8c8816957bd3f2","datavalue":{"value":{"entity-type":"item","numeric-id":6077055,"id":"Q6077055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$26FEC65B-ABEA-4EC9-AD44-043166A84592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"443cc822cea4a0703f7bb06becb988a202c11463","datavalue":{"value":{"entity-type":"item","numeric-id":252624,"id":"Q252624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$67E0D203-D37E-4A0C-A099-1EC7904057F9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$CF36FCA6-7510-4035-8DF8-66E5304FD057","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f159de156c29b3b40d3f017379c75305e2772f01","datavalue":{"value":{"time":"+2024-02-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6121107$8547D7DF-F4F4-49B1-B070-DCFB71505E54","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0b29270c94d2a1e58faf7afe2f98427f922187c2","datavalue":{"value":"https://arxiv.org/abs/2211.13790","type":"string"},"datatype":"url"},"type":"statement","id":"Q6121107$0DA16D52-956F-40FB-A771-ECCAF5DDBB7A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121107$6BCED5D2-5756-4721-9C04-FB62BF313EC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"26ba4f06ff5c7e92bd3a85f32aa625ae214ffe0f","datavalue":{"value":"05C31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121107$10C8C71C-70C8-4CB8-9D19-7A08B1594965","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0ae69032aaf224033fab591d81a55890d28a1b91","datavalue":{"value":"7809280","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121107$F9467075-D11D-4DAB-A714-DAA07D9835E8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa2a05ceaeae5e65348e6661d6a6ca26aaaa4f5f","datavalue":{"value":"\\#P-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q6121107$A7EDEA79-9B5A-4706-9008-590BE74DF20E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90b8a09be57ae85ca4701e8363941e782083b4db","datavalue":{"value":"approximate counting","type":"string"},"datatype":"string"},"type":"statement","id":"Q6121107$1AE4BF06-5D72-4AFB-9FA5-01C956EF2B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50940ff582f152d511fd3e73cca71bead0f1bf00","datavalue":{"value":"chromatic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q6121107$F10E384A-4AE8-47EA-8CBF-FB6FEB08FC9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6121107$1BB1F8FB-BFE5-4495-924D-B58458949368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1976f1378c55759244812e0b3a3c899c56ea76c9","datavalue":{"value":"Tutte polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q6121107$03C37703-A984-429B-BA85-0F958F9F58F9","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":"Q6121107$61891540-A383-47D1-854C-E52C2ECB25DE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"61d277bd2334b027aaa6a815a4a378969c07cd70","datavalue":{"value":"W4390986120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121107$0C026423-4902-4F09-B7A6-5C2CAD4E73DD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f480f36e78638d6d08f9507bd0215166231863bd","datavalue":{"value":{"entity-type":"item","numeric-id":511202,"id":"Q511202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$0523DE89-01BB-4CCA-BDB1-BA411874F067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3b89ad28ae974d117bf3fa6de69faa889ea31f3","datavalue":{"value":{"entity-type":"item","numeric-id":6170518,"id":"Q6170518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$C0B4BEC0-7349-482A-8EAA-2D1F9FFF89B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6f6c0c005489f8c1cb48ac3f49c4899349be70d","datavalue":{"value":{"entity-type":"item","numeric-id":5129229,"id":"Q5129229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$A1FA81F2-5A80-41BC-9DF5-46870A3A6914","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a386d5ef36b056e4a1668fce667fe8d1bca7a2d5","datavalue":{"value":{"entity-type":"item","numeric-id":5839327,"id":"Q5839327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$AF95B33B-6E26-4CEB-9D13-E128BCDE6465","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ba5a28bba639d8abf9ec3fc5a32da66346a5458","datavalue":{"value":{"entity-type":"item","numeric-id":2238459,"id":"Q2238459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$099E2059-C9BB-4A00-83BF-A97DE2850629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"586f10d130de482f357d2c74372d1d102ea11626","datavalue":{"value":{"entity-type":"item","numeric-id":5028870,"id":"Q5028870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$D8025029-D95F-466C-AE5B-F0067AB1FCD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c41869757e3ca2c7ab87060402b3a7db31c40a","datavalue":{"value":{"entity-type":"item","numeric-id":2323523,"id":"Q2323523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$06F82C00-AA12-4D91-A7E0-21C7C62245DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b985a626d3f8dceba9a158d188f71927dbb5e609","datavalue":{"value":{"entity-type":"item","numeric-id":3512601,"id":"Q3512601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$82633BF4-9360-4FDF-8ADB-A5DEB30AFB03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5acb4a5b823fd159ec456276526414b72f05ac02","datavalue":{"value":{"entity-type":"item","numeric-id":5866450,"id":"Q5866450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$DDF4CBF2-A2AD-4F9C-B4AC-88F680CC8EC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51d45a0d82ae9a043947779cd0f8c564fb83acb9","datavalue":{"value":{"entity-type":"item","numeric-id":2125077,"id":"Q2125077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$3C2965DF-8D44-4476-99E8-34DE7D44FE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"444d726f38cea97c77c64afd7d54c0868ec7bd4e","datavalue":{"value":{"entity-type":"item","numeric-id":1686832,"id":"Q1686832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$FA642929-246F-4433-95A6-8F67E8D06756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fee0825e850aa14b4336eb2bfcae7802db8aa26c","datavalue":{"value":{"entity-type":"item","numeric-id":937302,"id":"Q937302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$F3130509-012C-4118-BCE5-2047F1B19834","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c68cc3e0434f4b91a5b00f1b19ccb04b054c7836","datavalue":{"value":{"entity-type":"item","numeric-id":1926110,"id":"Q1926110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$EAB2E0CA-9BAB-4542-9D09-243169E52D24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4a995d45447632d59efdbcb8f068587544edcf","datavalue":{"value":{"entity-type":"item","numeric-id":5112588,"id":"Q5112588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$D5CFBC9F-C351-471E-8AAA-5FAA4B4DFFFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d8300e2819c55bd51f986df487003939dd294c3","datavalue":{"value":{"entity-type":"item","numeric-id":1932470,"id":"Q1932470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$14D8892C-72EC-4AC4-A90C-AF5DCC76DDA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d1eb3d868d04fb0bc6e3c75d517ea4c314251ae","datavalue":{"value":{"entity-type":"item","numeric-id":4712248,"id":"Q4712248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$87B2A3BE-853F-482D-BAFE-A1116746112D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b74a9f5c8eabae7b80425b1ac1775cdd8042ac6d","datavalue":{"value":{"entity-type":"item","numeric-id":3800157,"id":"Q3800157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$D33EC90D-60AA-4615-B4F3-5D8B55E697A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53a0aceb4d8337e7e5bda2e2d291f0d94b027b83","datavalue":{"value":{"entity-type":"item","numeric-id":315538,"id":"Q315538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$3CD51207-8C59-45F8-A2D4-682907C28CAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2496d76f7d7fec9d96f39f6e3a59ed93c78d8e95","datavalue":{"value":{"entity-type":"item","numeric-id":1165896,"id":"Q1165896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$3A0CBF30-399F-4C3B-905A-6B10526370A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8f4ac3f710aa0e3501adaea85266318426047f5","datavalue":{"value":{"entity-type":"item","numeric-id":2520840,"id":"Q2520840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$246FB8F1-D0D8-4C42-B300-1C9EB45D158D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b7afcb9a0497959937cf113b16fb13499994cb9","datavalue":{"value":{"entity-type":"item","numeric-id":4053736,"id":"Q4053736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$2C65C245-1024-4902-8DDB-D90E4AF04602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f366b34e210aba58eff9360c0d22b2ce2d5ecee4","datavalue":{"value":{"entity-type":"item","numeric-id":4602373,"id":"Q4602373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$F5C40DAA-378C-4953-B210-69F217069ED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8d4a8f559bbeea24e04bbe3b0f2c19542744c9f","datavalue":{"value":{"entity-type":"item","numeric-id":4554778,"id":"Q4554778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$02519DB4-8C8E-4AEC-A96F-ED0E90241C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9a3f5c7ddb59df0f44a9c8949743ebb557ee382","datavalue":{"value":{"entity-type":"item","numeric-id":2286792,"id":"Q2286792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$066D0488-491A-4D70-93D8-1CA4C7D03066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26d18ec19073446e0c21864d8e8d286d4effaee2","datavalue":{"value":{"entity-type":"item","numeric-id":3296755,"id":"Q3296755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$D228E940-D5BE-43F5-9C24-1FCE703D0054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d66501394617cf7ca5f021d9c48c0dd81dc83665","datavalue":{"value":{"entity-type":"item","numeric-id":3449868,"id":"Q3449868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$1717D053-9FCF-421E-A651-4AE21D49F7B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63035f667bb83d7376e59d7cfe44a458da98f97d","datavalue":{"value":{"entity-type":"item","numeric-id":2722657,"id":"Q2722657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$4D86FA9F-8BBF-4C77-B53F-B1AA99B4C821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ab417156d114b2a364bd0f0993a83c4a0a55ba4","datavalue":{"value":{"entity-type":"item","numeric-id":4819237,"id":"Q4819237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$5477847C-FF4E-4E0B-9ED4-8136265CF0BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b45e795959c95bcceb1765615b0bc14fa1976c7","datavalue":{"value":{"entity-type":"item","numeric-id":3416249,"id":"Q3416249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$4B4591B7-A501-4C9A-93E7-2A2B2D979504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e73dbdba735b48e12732b9669ad6ef479339545","datavalue":{"value":{"entity-type":"item","numeric-id":1382036,"id":"Q1382036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$EA6DF341-A13F-4162-A889-6E3FBE2CBEFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a850f345ab67dfb2c17804a1c4c534ac79e02217","datavalue":{"value":{"entity-type":"item","numeric-id":4372998,"id":"Q4372998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$C60CF4AD-76DF-4EA7-B79B-E4C6EBD8764C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0707e870be1740dc2a660ac4c8fe1afc6829703","datavalue":{"value":{"entity-type":"item","numeric-id":5634007,"id":"Q5634007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$FEFE451C-E68E-4E4E-9617-E834848F2913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76d17cdc84d5a7c88fde84de7f32f71667e04184","datavalue":{"value":{"entity-type":"item","numeric-id":5470709,"id":"Q5470709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$CE416B88-2789-4520-A972-68C7ECF97040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e857f2ea6e1da896ea7dfdd1ff3c3890eddfdb92","datavalue":{"value":{"entity-type":"item","numeric-id":4157394,"id":"Q4157394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$F0571DD7-9214-466E-BE4E-EF6A989FDDAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bc99925d78cbc1381e3ed8820beb3201b0422b4","datavalue":{"value":{"entity-type":"item","numeric-id":1366787,"id":"Q1366787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$4D3DE2FD-7474-40B9-8B25-9652913BC402","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9700158a87447cbeeffedb3a67f6cc3299e703b1","datavalue":{"value":"10.1007/S00037-023-00247-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121107$FDABEA76-077D-4F77-AD0B-2F2D10B92772","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121107$D400BB6D-CDAF-4570-9FD6-C67FEC9F4AA6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6121107","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6121107"}}}}}