{"entities":{"Q2927657":{"pageid":2938377,"ns":120,"title":"Item:Q2927657","lastrevid":58062468,"modified":"2026-04-03T16:00:58Z","type":"item","id":"Q2927657","labels":{"en":{"language":"en","value":"Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6365539"}},"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":"Q2927657$8C7C5640-4FCA-4899-9F47-5C1402A500CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3e9d199d13ab224fc7dc3d71a7e58898ec16cb0f","datavalue":{"value":{"text":"Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2927657$62707894-2213-4514-BA28-80E9A9748B27","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"87ee1a736f2617a8230621844516c30f31bb7b04","datavalue":{"value":"1303.68074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2927657$1B70B27A-6CC9-4B39-B871-BBF910571A43","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"107f5b5dc660591d3fce938c0f2d28cd0abac47e","datavalue":{"value":"10.1007/978-3-642-35843-2_29","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2927657$FD4082F7-7ADA-47DF-A201-48536E9786DD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"01c7c91a252c5355934715212b81e739aaf74478","datavalue":{"value":{"entity-type":"item","numeric-id":261371,"id":"Q261371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2927657$B09546AE-3B47-4CB3-897C-FD4629E1B78A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8112a4884ac488e222bb031fe5d75202a7b6dcb","datavalue":{"value":{"entity-type":"item","numeric-id":389952,"id":"Q389952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2927657$B5551480-6178-4C86-8E05-B313E37C72E5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2927657$DA5A1218-9815-47DF-BE9E-53831F68E111","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"05abf2dbc2f0a908bef50ea9b8f6fae21a49dd4f","datavalue":{"value":{"time":"+2014-11-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2927657$3C50AEBF-4CBD-44A7-A028-A9D66FD30CD2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"78dd189aa7f7037275501f73f990ea676ff1c61a","datavalue":{"value":"https://arxiv.org/abs/1202.4665","type":"string"},"datatype":"url"},"type":"statement","id":"Q2927657$DD0ACA3A-087A-4AC2-B5A6-250256E844D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d4eacf16ddf333b08ebeae1bf532182a985567a9","datavalue":{"value":"http://dro.dur.ac.uk/13469/1/13469.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q2927657$0E484649-D9D9-4277-8317-698C5EC77B44","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2927657$5514D4C3-C98D-43BE-A832-EB01BEABA361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2927657$775E98E9-9B99-4176-8F2A-E2E59D47A781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2927657$4B5F67FB-E595-4886-8568-340F3EA0DF37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2927657$CF19B0F5-AB16-4897-9C66-7F70FCA39C14","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a7cbd60de994370138dca2a225a348e16ecadbc3","datavalue":{"value":"6365539","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2927657$BDDA5A60-94F7-4839-BF04-ADC1544F57B2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78de82af7c99d6c8e3e2822a393eca8596efe61f","datavalue":{"value":"3-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2927657$F265B76E-3EEA-4AFC-8600-785C9E6211BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e52d2a0535cd7a532d1c8b4725c6157993eb017b","datavalue":{"value":"graph diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q2927657$FD2CE986-4DFE-41DC-AD2C-50D865AEF141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a88d74d9d319e69d92e1e9b771809ad08ab13c8","datavalue":{"value":"graph radius","type":"string"},"datatype":"string"},"type":"statement","id":"Q2927657$6936C552-2AEC-49F9-84E1-DD50058DEF31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f7a17ae254ce46a1415408c6f61c7ff892a5e04","datavalue":{"value":"subexponential algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2927657$5CF5CF92-7AAD-4271-8AB6-C2D1FAB3B8E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q2927657$0BFFE661-0DC0-400C-9D3E-688F86B66C44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b0974d841ba27603503b56afd092463f7ab4b17","datavalue":{"value":"exponential time hypothesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q2927657$CDC40CA7-CCC8-4A95-A555-7A6657751968","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":"Q2927657$01F4174A-6AC8-4172-836A-F0FF69D59B44","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"617c0aa7916fb3aadc4abbe9fc060b480698676b","datavalue":{"value":"W2401220501","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2927657$399FFC34-2E31-4A72-AEE0-586B63814985","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8c0c6036b3fb1c6ac260144a8b61a44985142ce","datavalue":{"value":{"entity-type":"item","numeric-id":261372,"id":"Q261372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2927657$3EC3A9F4-4A1B-48BC-9E3E-9A47F80CBF72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b319fd572858e9f3c375226686be9fd811d846df","datavalue":{"value":{"entity-type":"item","numeric-id":5866453,"id":"Q5866453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c688c5732b5cf2db1803b1dabdf62b133b6bfc2a","datavalue":{"value":{"amount":"+0.93772596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2927657$A0CDFBB6-AFC2-4B72-86E8-F04F76272BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20d227f7d1cb49135d7d58920d462fba3918435d","datavalue":{"value":{"entity-type":"item","numeric-id":6075926,"id":"Q6075926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c688c5732b5cf2db1803b1dabdf62b133b6bfc2a","datavalue":{"value":{"amount":"+0.93772596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2927657$4FFCBE17-C096-4897-84C6-B95D5DFBFEDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2c5585cac771075c1be0995310f18e108012d31","datavalue":{"value":{"entity-type":"item","numeric-id":290195,"id":"Q290195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cce44b5a855607e0a2fd7365e94beb64b813524","datavalue":{"value":{"amount":"+0.9160925","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2927657$8EAA934D-8351-4321-BE4B-3C134B3254CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67d100554ecc582fa36fe1df0a10dc1603e57fab","datavalue":{"value":{"entity-type":"item","numeric-id":5251923,"id":"Q5251923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e26fbdf5f12e8ee2136354e05765f04e12c5431a","datavalue":{"value":{"amount":"+0.91064036","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2927657$FF9E93B5-AC3C-4C4B-9CA6-D6EAF9EA5A79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c504f95b33855914aef11acf4f0265c56007f6d","datavalue":{"value":{"entity-type":"item","numeric-id":1281385,"id":"Q1281385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5801c1693c357f884631ba277a2de68929024051","datavalue":{"value":{"amount":"+0.8996062","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2927657$94C6A85D-404C-41B1-8179-32C838CB41F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d49cc07ddecd3b497ee69779441de7bed1538a34","datavalue":{"value":{"entity-type":"item","numeric-id":2081467,"id":"Q2081467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51ecce0e41adf0c07727d4e8242087c1aea6bb08","datavalue":{"value":{"amount":"+0.89532256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2927657$7AEB85F4-4BF8-46A1-8261-72ABE5387FE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4beabc9fbbbb4947b2deeab8530abda0afdab52","datavalue":{"value":{"entity-type":"item","numeric-id":975462,"id":"Q975462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c3d6674d91e982cde1fba53d0c16d779df6c78c","datavalue":{"value":{"amount":"+0.8928975","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2927657$8E1891EA-7832-4E31-AF3E-B782AC06F9DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b7d7c91a250e9f75c7ad1bf74c2f4a6f4305d00","datavalue":{"value":{"entity-type":"item","numeric-id":1944084,"id":"Q1944084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"529e23652c032fda55d755a7286f49bfd02b19f2","datavalue":{"value":{"amount":"+0.8870406","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2927657$E200ABA2-2C95-424A-929F-6767A93A7175","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2927657","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2927657"}}}}}