{"entities":{"Q1356685":{"pageid":1367424,"ns":120,"title":"Item:Q1356685","lastrevid":68540535,"modified":"2026-04-13T00:25:51Z","type":"item","id":"Q1356685","labels":{"en":{"language":"en","value":"On the NP-completeness of the \\(k\\)-colorability problem for triangle-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1019044"}},"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":"Q1356685$754D29A3-8F67-4B68-8963-E56FE77D2DC0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e0e5cbe176ad1388ad2d50d681976fc9833b9e16","datavalue":{"value":{"text":"On the NP-completeness of the \\(k\\)-colorability problem for triangle-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1356685$00D08781-96C3-4652-9A05-E199EDFF199C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8dd00bed21b7bb1515c54008e110346345c14f66","datavalue":{"value":"0870.05021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356685$0F3C2B39-9202-4F42-982F-8D78A5EAD323","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"875b34d830a3c408a681e48bb30a240b2dafbf1f","datavalue":{"value":"10.1016/S0012-365X(97)89267-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356685$1A6193BD-5502-4F1B-9BA4-0A35EFE2B6C0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec2d7eb4aa6a054061ffef53b12788916e0dba01","datavalue":{"value":{"entity-type":"item","numeric-id":222618,"id":"Q222618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356685$432AE3F3-E9F9-4699-B04F-D4D3A78628AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6eccd330e58db916925e9726f6d3cc506f17a2da","datavalue":{"value":{"entity-type":"item","numeric-id":442401,"id":"Q442401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356685$60A12398-DADA-4153-82D0-08AAECF0DD63","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356685$987D5491-597A-4200-8EB0-C16611257785","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dfb3a2440187ce324054f87424416efa61e67ba4","datavalue":{"value":{"time":"+1997-06-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1356685$A206A7E0-BE37-42AC-83B3-68594E4D544F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356685$CBBCBBEA-8619-4D5D-B1DE-A833E5C3366E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356685$3068948C-B350-4CB1-8CF5-CAF152B30BD0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"411f45d81e6e10d26dea46e76993209e410a7aa0","datavalue":{"value":"1019044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356685$A8D6A7EA-8706-45FD-AB1E-8C1DE2618E6E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f22b3a770a8e0f957adbea77b1365a9ec85120","datavalue":{"value":"\\(k\\)-colorability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356685$1F9D966E-791F-4371-A220-59713AEA4759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e622aeaba63f6c6aeab16997f6b077b4a104e13","datavalue":{"value":"\\(k\\)-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356685$C8754EEF-8FC6-4E8E-8DC9-D2E82BCAFEFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"561e6329db45dbe88108c0aa91fc69c5266fa2f0","datavalue":{"value":"Brooks' theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356685$23E66FA5-07FB-4D86-9040-1829D2A18FF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356685$2CF5BDDE-9FB8-496D-9FFE-37EB51CBC292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"938507bc54d83812726579a12a77d5cd2af4ae8b","datavalue":{"value":"triangle-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356685$CCD80FCB-F6E8-49A9-9C26-A6714FAFB1CD","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":"Q1356685$463CC1BE-DCDD-4FE1-9FD3-0B79440F3DA5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a92ab907df072bb20a1057061523b1fdda43679","datavalue":{"value":{"entity-type":"item","numeric-id":5782525,"id":"Q5782525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356685$FE7F4377-FB37-4488-9F28-99CE4B46AA7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5713d2776eeff8472738ae00256613e738da003c","datavalue":{"value":{"entity-type":"item","numeric-id":5589117,"id":"Q5589117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356685$9315C311-F095-4852-9773-B438F51F535C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfcd789034b4d0e087e6cadd8049749ea1357e3a","datavalue":{"value":{"entity-type":"item","numeric-id":4050624,"id":"Q4050624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356685$37381AF3-3B90-4CF0-9FAE-A91A006885E6","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":"Q1356685$591FCD5E-21E5-4068-9E07-AD2062196263","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"744eb473a22c56b89611567e61bffe888ad14756","datavalue":{"value":{"entity-type":"item","numeric-id":2625676,"id":"Q2625676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356685$24D3782E-DDEF-4569-AE5B-8BBE1DCB24B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356685$91048542-D9DC-4588-89B0-E3A2D67BCD52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49245e0aa29f3d0b8a4f3aa138d592837bd9a7fb","datavalue":{"value":{"entity-type":"item","numeric-id":4083461,"id":"Q4083461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356685$8065F85A-2037-47E2-84CA-B0D550E3A7B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dc8e3a70353874ae71b2b5e055e522ed5b6378c","datavalue":{"value":{"entity-type":"item","numeric-id":5847741,"id":"Q5847741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356685$F3448892-95F5-42F2-B448-3EC129E1FAD7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f13c0f62b64271903567e6cd4205c4ef73d63f00","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(97)89267-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1356685$58E479B6-8F96-4EF8-B312-6160716E6D77","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2db47626cc69f80680175672fc55bb1dbd77bfc3","datavalue":{"value":"W2068121436","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356685$7E2727C5-6A2D-41D8-BB68-F8E8551A300E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d5532fc5495154adad1b08303e655fe57b63cba","datavalue":{"value":{"entity-type":"item","numeric-id":3057624,"id":"Q3057624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9588475198f0db80824ce948806a566ff968668a","datavalue":{"value":{"amount":"+0.8720890879631042","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":"Q1356685$E0916EEC-3C6C-47DC-A2FE-CF4862484EE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24678519c91afdca719e5537484100d1170838d3","datavalue":{"value":{"entity-type":"item","numeric-id":1354146,"id":"Q1354146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e864d92683a306ec3d2d5977d55155d88156e8e8","datavalue":{"value":{"amount":"+0.8633198738098145","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":"Q1356685$CD17B587-FECC-4630-9DCB-DEEDF3A07080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"348b3ca43084ae052cca73683ad8ea45b98cd500","datavalue":{"value":{"entity-type":"item","numeric-id":3070909,"id":"Q3070909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51aea729c3e14ecb003ead43f0ca8223b0fbb028","datavalue":{"value":{"amount":"+0.8573104739189148","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":"Q1356685$F8E36E78-3CE0-4D9A-8F3C-611A6E531B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"041459200b72a47dfea0c46e675cb3fb1a37ae8b","datavalue":{"value":{"entity-type":"item","numeric-id":4429678,"id":"Q4429678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"930c7a4e9de834e745144592b9a86f6a3b190100","datavalue":{"value":{"amount":"+0.8478111624717712","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":"Q1356685$59D2F7C1-3598-4EB0-9F62-58FBF0E1464C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4d216156c5333f6fda9bf4df9d8ba006313bb0f","datavalue":{"value":{"entity-type":"item","numeric-id":764907,"id":"Q764907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f005590222fb4f208211d37715519bac3894bbcc","datavalue":{"value":{"amount":"+0.8331617712974548","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":"Q1356685$33F57BB8-AC7C-409D-BB86-874B186A513F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the NP-completeness of the \\(k\\)-colorability problem for triangle-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_NP-completeness_of_the_%5C(k%5C)-colorability_problem_for_triangle-free_graphs"}}}}}