{"entities":{"Q730005":{"pageid":731854,"ns":120,"title":"Item:Q730005","lastrevid":63933603,"modified":"2026-04-11T16:31:22Z","type":"item","id":"Q730005","labels":{"en":{"language":"en","value":"Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6668321"}},"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":"Q730005$FE655C19-FAE5-44EB-9A5E-66041E755429","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9f7993ae79c934b3b6bd92a87579c0f0bc1e96ef","datavalue":{"value":{"text":"Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q730005$42D63526-473C-4505-957B-B81A38364560","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09c93289d80b252eb88d975937a7bc3bca11a703","datavalue":{"value":"1355.68106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q730005$3F77BDBF-6DF0-4542-82B2-C6EC065B4123","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"73a2468ab546d0f64591ae8a5ad0b2ad8e730787","datavalue":{"value":{"entity-type":"item","numeric-id":730004,"id":"Q730004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$D9443F43-FBA6-4644-AE30-5DF790846736","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$7E266058-D7B7-4EB0-A82B-E6AB2B8F8F12","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0580f4f311c0237caf7375ec327f848331aa70a3","datavalue":{"value":{"time":"+2016-12-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":"Q730005$3746F196-64C2-46BC-AD22-ACF55B4F5EB6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"78ffd5a0f12d9d9eb38f6619f747c00a7ff0cf5e","datavalue":{"value":"https://arxiv.org/abs/1407.7423","type":"string"},"datatype":"url"},"type":"statement","id":"Q730005$65CD9D62-21EE-40C8-A5A0-B49F94BE9FB9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q730005$8F04E714-57A7-4CF7-BE37-62931BC312B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q730005$439D4854-986D-4C22-AF8F-0CF898D5A812","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b6a0a8cf82dbe0efffbfa7187769ffe6369875ab","datavalue":{"value":"6668321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q730005$4B417D38-7061-48AE-ADF2-4742F72BB977","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q730005$7317050E-0B66-444B-981A-D82C9B5772C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5867ec7b44aefc01672736513dfe6410a0300cd5","datavalue":{"value":"SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q730005$93EA611C-5BC5-485F-9710-A977DCC5FD28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q730005$D81AFAA1-FC6C-4773-8456-3E73370D38FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5c22b74c5ac63ea85343bf5bfe79c4f4f0404e9","datavalue":{"value":"monochromatic cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q730005$6D3F3F95-04B9-4871-8CF3-DCAD87CAC891","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":"Q730005$1EEF201D-5868-4CDA-B05B-EF118AA1FC7A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"700ba7f0c3f5d1ee80bcf8bed7c55db6e3fea0e5","datavalue":{"value":"W2542720522","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q730005$8E2A7C7A-6426-4217-9AF1-841FB2B8CFE7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7222b7128910c79c75ce187afd05199714404b6f","datavalue":{"value":{"entity-type":"item","numeric-id":2498403,"id":"Q2498403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$236BC09E-AC98-4A78-872F-E480A27BC526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bdf0925a1f145a80043b4cb534c11e1bbbbadbe","datavalue":{"value":{"entity-type":"item","numeric-id":1978502,"id":"Q1978502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$4D2FF3C1-9D83-4050-A91F-E5C8802FABC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6d08598288352e29279544628065f4ee6040641","datavalue":{"value":{"entity-type":"item","numeric-id":5437903,"id":"Q5437903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$EBB6998D-46AB-408F-ACD0-250E13842353","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$D7BE9782-CF9A-47A6-8B2A-4B4C49BE7CB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31b0e6148c6711b4917a5d908c6a1cefaaa1c6b4","datavalue":{"value":{"entity-type":"item","numeric-id":759645,"id":"Q759645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$0D0DCF08-C477-40AF-A727-D6614D61B398","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":"Q730005$0AC36452-854A-4FB8-9C24-E35AF7D8382D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c00feefb902f81a468b517c44bd157d2e5eafad","datavalue":{"value":{"entity-type":"item","numeric-id":3225711,"id":"Q3225711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$532DA869-3B0B-4FEC-BFFA-015156622BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32669c9303b6fcfce30a867e0ec9585dd818044e","datavalue":{"value":{"entity-type":"item","numeric-id":3878752,"id":"Q3878752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$164A9EEB-FF69-49BF-A6B8-F1D0B5564DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"251cfc761b6feb8831cd63e767e18a01fc471eaf","datavalue":{"value":{"entity-type":"item","numeric-id":2815462,"id":"Q2815462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$A42DD77F-EBA8-43EB-BB61-10FC0AF4976C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$22C26367-0E5C-4991-9EAC-1D4AE10893A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"820f43e838f36e4751380bfd28125ba71c80d275","datavalue":{"value":{"entity-type":"item","numeric-id":958693,"id":"Q958693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$2F443CBD-13D6-4E5C-A1F5-E0B9194C6832","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cf087baec79486460b449579f43e426b0623cc4","datavalue":{"value":{"entity-type":"item","numeric-id":4232836,"id":"Q4232836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q730005$F6D68DF2-772C-4AF6-BC56-7B611DEBE196","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b1ac2104a1198a0cc793c261a37ec14fa91e7edb","datavalue":{"value":"10.1016/J.TCS.2016.10.011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q730005$EBBDF8C6-11C3-4A96-8965-A2B82F7E2991","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a5340e012d8cc50a4f29e578ced0baf0fe588cb","datavalue":{"value":{"entity-type":"item","numeric-id":528481,"id":"Q528481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aaf3b1485504fccb8167b8498d89312048ebcac","datavalue":{"value":{"amount":"+0.8954586386680603","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":"Q730005$7B51A229-B6F5-43C2-9021-281486C46597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7033d97d92185f53505832b6d8383be4176a484a","datavalue":{"value":{"entity-type":"item","numeric-id":3558598,"id":"Q3558598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68b5ba67fb51f411f287d216a5fecfa204644910","datavalue":{"value":{"amount":"+0.8168275952339172","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":"Q730005$C01D51D6-B465-44AE-B74A-302F780CD69D","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":"71d2faf4efa36a7b39ae19945b2d038ae5507c3d","datavalue":{"value":{"amount":"+0.7931596040725708","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":"Q730005$A3256077-A5FF-4093-B05E-51E841BCFB7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0442060007113cfca36c0717e8228da49ec67d83","datavalue":{"value":{"entity-type":"item","numeric-id":2136878,"id":"Q2136878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee27412b5ba8e1801fc5030c465b201347d90d6f","datavalue":{"value":{"amount":"+0.7870927453041077","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":"Q730005$7F9B14BE-ABEC-4CF8-8405-1FAE6EA84D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3f166cb0cb4be9c2dcaebf291d22b755323ffed","datavalue":{"value":{"entity-type":"item","numeric-id":1891685,"id":"Q1891685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2429195d33da6f5bcad8f50d09962b0f3ddba53f","datavalue":{"value":{"amount":"+0.7821221351623535","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":"Q730005$68389700-B494-4BD3-B4F2-6A533C860F30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Vertex_2-coloring_without_monochromatic_cycles_of_fixed_size_is_NP-complete"}}}}}