{"entities":{"Q261372":{"pageid":263139,"ns":120,"title":"Item:Q261372","lastrevid":60526149,"modified":"2026-04-10T17:31:52Z","type":"item","id":"Q261372","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 6559785"}},"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":"Q261372$BE12F09E-8D33-40F8-B505-D8E22EBBD735","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b42e06804c2e51d087c32cea6612bd3c24f13a53","datavalue":{"value":{"text":"Algorithms and almost tight results for 3-colorability of small diameter graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q261372$C94D0648-83FF-4D20-9C18-15121A4EEB13","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5c808e52a50a443296abab77b7c29515684927a4","datavalue":{"value":"1336.68142","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q261372$79EB2C55-7E14-4711-84AB-751FD9664143","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":"Q261372$268E4BF0-64FB-40E9-A6A1-E48E67253E79","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":"Q261372$F678C542-ED3A-45F2-855A-40E09D88174B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$2EC2497C-D2C3-47D4-8524-4DF0E877B554","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d4e0833fdb30e5d55a1ed86554b76ff3f3cdc33c","datavalue":{"value":{"time":"+2016-03-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q261372$E1D90665-76C7-4A75-901D-5A352E2B809C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q261372$4F6AF0D6-DCD5-4048-82F9-E33FC5B53C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q261372$5490FAEC-5B81-419F-B856-8D7C8BDA1035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q261372$86486CFE-BE36-440E-B917-CBD8702CF841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q261372$970F4DD1-2184-4940-B589-EDED8BE34C9D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9895aec664378b4b81147320dcc719bc38caf1af","datavalue":{"value":"6559785","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q261372$F1374466-A16C-4BF5-B6FC-36484C26F304","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78de82af7c99d6c8e3e2822a393eca8596efe61f","datavalue":{"value":"3-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q261372$BCBB923C-6292-4550-9DF3-A9ABF196CF84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e52d2a0535cd7a532d1c8b4725c6157993eb017b","datavalue":{"value":"graph diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q261372$72EB6FC7-BD39-4572-BB8A-DED96FB59A07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a88d74d9d319e69d92e1e9b771809ad08ab13c8","datavalue":{"value":"graph radius","type":"string"},"datatype":"string"},"type":"statement","id":"Q261372$5CF87427-8445-45C2-96FC-11768346E90F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f7a17ae254ce46a1415408c6f61c7ff892a5e04","datavalue":{"value":"subexponential algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q261372$5B23AE17-629D-41BC-B633-B905EBB2C7AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q261372$42F8AD4A-9AB5-4F20-A89A-999939E8C281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b0974d841ba27603503b56afd092463f7ab4b17","datavalue":{"value":"exponential time hypothesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q261372$D8A05E28-21C7-455C-A91A-90B6F53DE8EB","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":"Q261372$E78F1127-6CC7-4EF6-B310-6614E1ADC9FF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fd79bd1fea17479ae5ff56826d0effe56d8001fd","datavalue":{"value":"https://doi.org/10.1007/s00453-014-9949-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q261372$BCEFFD00-7B91-4B81-977D-EE134FC67662","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"be2d9a86b47151de52341261b8ff3ddc514cf8c7","datavalue":{"value":"W1873654474","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q261372$A6916287-D2A6-4EE7-ABE6-48ED6EF11A91","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2809216b6234e91ba0978673c896d9ca1b9f90d0","datavalue":{"value":"Q59476848","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q261372$C85946C4-4841-4788-AD70-AEEC4AA3AD53","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4716c18b855b39ddf407937ad9cdd888b69fb46f","datavalue":{"value":{"entity-type":"item","numeric-id":1813713,"id":"Q1813713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$181A8FE4-7250-4E58-9366-DF51C6F6C661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2758f48b1a93e71d851a0e4b14bce521c35fc05","datavalue":{"value":{"entity-type":"item","numeric-id":3503433,"id":"Q3503433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$E20A55D3-1EFE-41DE-9349-F0E6F78A4CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d321a0c64aaebb2b65e690124a4b66580f4c126b","datavalue":{"value":{"entity-type":"item","numeric-id":1944084,"id":"Q1944084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$36123970-25CA-4A26-A1EA-8E09F8193450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c474c39c66015d4e536570f84c99c108f36d115","datavalue":{"value":{"entity-type":"item","numeric-id":4652410,"id":"Q4652410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$EFADB5D1-FC2A-4E44-B717-4ECD6A1F88CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f92a64324b680cc8236beb143a28fcd1f34aade6","datavalue":{"value":{"entity-type":"item","numeric-id":444433,"id":"Q444433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$026179F0-9668-4DB2-B36F-34D0B4FE65C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c730226151467cb2e26a5a485cda3ea30bf5de27","datavalue":{"value":{"entity-type":"item","numeric-id":3936765,"id":"Q3936765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$2C6E2EBC-F13F-4C05-89BB-EEFF6D6BAC1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f835811f95d982ee903d207da9d809dc55bcb95f","datavalue":{"value":{"entity-type":"item","numeric-id":3651537,"id":"Q3651537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$4A4A848D-CFD2-468C-8456-4F2B8CC7B65B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1134f2341d7e5000fd707505605e06ca29388803","datavalue":{"value":{"entity-type":"item","numeric-id":2641288,"id":"Q2641288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$F6F658AE-71F8-4041-AFCF-5BAB18FF402B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d4bd16b8f988e4232f1989a0f22132674569ade","datavalue":{"value":{"entity-type":"item","numeric-id":1079363,"id":"Q1079363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$C9A249E6-C411-4E16-9117-EC857EA857F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08679e1302d53c12ee04f803b2320a1e4c7b1a0b","datavalue":{"value":{"entity-type":"item","numeric-id":606873,"id":"Q606873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$377D9612-EFD3-4ABD-AB9C-5DDE2FC678F2","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":"Q261372$85E1CA59-1487-475A-A088-C38A8DAF25DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$96266AC5-7DDD-4D6B-B8E3-D121BB80A941","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"977cd433ecde040f39e4c4dde1c0b893e5757f3f","datavalue":{"value":{"entity-type":"item","numeric-id":848637,"id":"Q848637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$1005DA03-1489-431D-8F26-D285F4B63B99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$223B27BA-2BFA-4283-8286-E41ED5909C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"112fa1e16c28072d1b690d88a68f10e9a878f19f","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$B091E59D-D53B-45F9-8394-41E52C7B9000","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4548ea5d583917c0fa9b6aaa6b1d48c80c1e7e","datavalue":{"value":{"entity-type":"item","numeric-id":1604206,"id":"Q1604206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$A28EFE02-6D66-4038-87C5-03369F4C4199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd6f205a11f3d8ebe2e6f8fd38842f98916ec8b9","datavalue":{"value":{"entity-type":"item","numeric-id":4904144,"id":"Q4904144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$51E3E6CB-A06C-404E-A647-736490D6CD2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fec6d5d27c48b92a86d66707db8bd5dd67fb137","datavalue":{"value":{"entity-type":"item","numeric-id":1356685,"id":"Q1356685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$D6E4CB9C-75B0-47C2-899C-2C29FB0E2298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$91C2AC5F-3B0D-4F5F-8C7A-A4D00C66D787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"402db5507dedffef5c7e618fb72c652f28535d49","datavalue":{"value":{"entity-type":"item","numeric-id":4108373,"id":"Q4108373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$4BB5EB2A-AA94-49A3-9399-FC85418E00BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b97ec674c9801d3e945638d7eae4a8579650e83","datavalue":{"value":{"entity-type":"item","numeric-id":1427186,"id":"Q1427186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$84F7CB0D-8319-49E3-8910-A65C1BC7007C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff3bbeca2eff4b963d9057c96f739c612a4b8643","datavalue":{"value":{"entity-type":"item","numeric-id":1934316,"id":"Q1934316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q261372$435447BD-6D13-46CA-94C5-6C5BB928CAF2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"68a69786b8d337c092f280f3770a2779b79710a6","datavalue":{"value":"10.1007/S00453-014-9949-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q261372$397A451E-AD32-466D-B33D-32C6BC96FD27","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57c9247899b145b33ec5ff81e3d5c5a1a1d6762a","datavalue":{"value":{"entity-type":"item","numeric-id":2927657,"id":"Q2927657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f3a670c034df031c7bc0c700d4bfbd205f8688d","datavalue":{"value":{"amount":"+0.986583411693573","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":"Q261372$4098AA45-D01B-4BEB-B19B-1BE908E8E701","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":"e8795294c86e2d7c8b81926d802500b4c968c57b","datavalue":{"value":{"amount":"+0.9189725518226624","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":"Q261372$4ACD6B5E-CC78-4043-A757-A36708C91A9F","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":"5d630a8698aad765be10c1d64d21c67402ade5a3","datavalue":{"value":{"amount":"+0.8249622583389282","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":"Q261372$5F717314-0F06-4B3A-AA6A-E05434AAB4AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7ac0d140435ad759e6b184ffc5dfbc8af1b4029","datavalue":{"value":{"entity-type":"item","numeric-id":5918661,"id":"Q5918661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8e8b3a54fb7924ed017799cd32bb8f5ef7332ac","datavalue":{"value":{"amount":"+0.8184970617294312","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":"Q261372$D2604AB0-07BB-4359-89CB-E7CBADF4A1EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33f51f546cf70beb070ddcabd972cdc55256292a","datavalue":{"value":{"entity-type":"item","numeric-id":2028085,"id":"Q2028085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c76f31efc2f7af62e84ed89d2e7120477b6aa585","datavalue":{"value":{"amount":"+0.7706122994422913","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":"Q261372$5AE34DF2-14C5-41A0-B0B1-CBBCE6670691","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":"Q261372$03ADA28C-D9B8-42A1-A957-8ACB763DDC5C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithms and almost tight results for 3-colorability of small diameter graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithms_and_almost_tight_results_for_3-colorability_of_small_diameter_graphs"}}}}}