{"entities":{"Q1071025":{"pageid":1081777,"ns":120,"title":"Item:Q1071025","lastrevid":77802011,"modified":"2026-05-06T10:05:23Z","type":"item","id":"Q1071025","labels":{"en":{"language":"en","value":"Coloring perfect \\((K_ 4\\)-e)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3937192"}},"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":"Q1071025$4BD32DDA-0A78-40B6-9E62-A79587B79397","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c01c691b9bb5000dae01f9f315faee794c709e5e","datavalue":{"value":{"text":"Coloring perfect \\((K_ 4\\)-e)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1071025$F8EA6DDC-8E4C-4B4C-A9E4-63EEE6E051A6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"178eeeb7ce7d5e1853917561d4db5ac6c8f1531d","datavalue":{"value":"0585.05007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071025$455F49A1-1B0E-4A02-8539-BF20CD2EA1A7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9312bdc56599455812596cbae6a2e7aceb4b78ca","datavalue":{"value":"10.1016/0095-8956(87)90048-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071025$62850142-C7CC-40F8-BE1C-F443C8CF85B9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071025$5B046793-D99D-4399-B672-46FFEA78DC3B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1071025$C6C0A01E-AE1A-4622-995A-3FEBDBBF049A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"050d6f9d44289ffbc268cf5e1bf4aa515800d9dd","datavalue":{"value":"This note proves the Strong Perfect Graph Conjecture for (K\\({}_ 4-e)\\)- free graphs from first principles. The proof directly yields an \\(O(pn^ 2)\\) algorithm for p-coloring perfect \\((K_ 4-e)\\)-free graphs. (Note: a previously published proof of this result by Parthasarathy and Ravindra is incorrect.)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071025$C552A024-556C-4A9F-B626-F4A85ED5B88B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071025$F18F86A8-AD8A-40D8-BF39-2F791201D549","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071025$755901BD-5FA3-4A86-B03D-A420AE5E6A8B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"54e645680e5a801be86d2b6ee01953565b35c777","datavalue":{"value":"3937192","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071025$DD33D9C8-1ED2-47D5-BF69-B4B3FC263016","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a11116a6b4821127d46d686f666f969b50e0a4e","datavalue":{"value":"strong perfect graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071025$A7CFD72C-6E59-4DB3-AEB7-9186E04134A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071025$768BBE74-A114-4714-AEFE-B09D2F448E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071025$ED4C77F1-0CBD-433C-B778-8C58DC11DC69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20ec9b7c00af8db6eeb0df0952bb2d72b71ee8cd","datavalue":{"value":"(K4-e)-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071025$2AE51E22-E344-4D8E-8B9A-0CA04E7707B0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be5b5a53473a332bcbde980d9c723a51b6f798cd","datavalue":{"value":{"entity-type":"item","numeric-id":1110542,"id":"Q1110542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071025$7B387C0C-3905-4219-B41C-A49214644DB8","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":"Q1071025$D7E43EEE-11B0-489E-A2EC-80DB7213B7FB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"103074f32740d7716b254663bb64e86791f942ff","datavalue":{"value":"https://doi.org/10.1016/0095-8956(87)90048-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1071025$420C7200-ADD4-43AD-926B-58772EA9E696","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f66e15ddf15f22faf3598ab7bcf3c52b96e0d43b","datavalue":{"value":"W2093266461","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071025$23A06C5E-9C70-4306-9B52-03B0A4068E71","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071025$3F5B2CF5-123B-4B80-BF91-9A3714E75B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071025$77957E28-7DAD-44C8-BC03-5A49F7BD4ECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b3c99368ea38ef93edcc839b4081d214aa7efc0","datavalue":{"value":{"entity-type":"item","numeric-id":2553372,"id":"Q2553372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071025$8AF0B0CE-C072-4473-970D-372107D8C713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f2ea9e473a8cf61f64728aa7c6cf40b378a168a","datavalue":{"value":{"entity-type":"item","numeric-id":754232,"id":"Q754232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071025$AA1032EA-2BAE-43DC-91FA-F361B94E723A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f82f1d58a378c5c11a10b3fe3cd8aab9c0bad226","datavalue":{"value":{"entity-type":"item","numeric-id":1096639,"id":"Q1096639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"231ba2d94970a6c3a925c20f0c5e75d0dab7a402","datavalue":{"value":{"amount":"+0.8888644576072693","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":"Q1071025$0563685D-CE42-4D57-A00B-1EF0664825C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"630e54c7fa45d42d2c208689f0ac8600b3b95f15","datavalue":{"value":{"entity-type":"item","numeric-id":4731202,"id":"Q4731202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"995604a53d64c83a2f4c58313bd3951c34059499","datavalue":{"value":{"amount":"+0.8641067743301392","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":"Q1071025$ECAED413-F951-40CE-8D1F-1D3B8F049255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e393bd4c8c5ee7f2b8a0325ae28ba43220ba6b4b","datavalue":{"value":{"entity-type":"item","numeric-id":5937451,"id":"Q5937451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cc68ac52e680e73e8dfe3e226e67e46eafc7edd","datavalue":{"value":{"amount":"+0.8335927128791809","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":"Q1071025$D9FF6DF7-F555-4C58-8602-0743F1F2C65F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc20b62cb9c6b85fbe0b1784833623ce37018561","datavalue":{"value":{"entity-type":"item","numeric-id":5903942,"id":"Q5903942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"239ecc21ac7d54c910d59e8280bcd4f29dcf0739","datavalue":{"value":{"amount":"+0.8304208517074585","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":"Q1071025$03E73739-36E5-4040-BC86-77683E82FFB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a273554074f4861257c9cf9db6742f646253a2c","datavalue":{"value":{"entity-type":"item","numeric-id":1382811,"id":"Q1382811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff3425d56ce8637f0ad95ddda0235bcdc3cc668f","datavalue":{"value":{"amount":"+0.8236178159713745","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":"Q1071025$EFE6E94B-15DF-49E7-9DBD-5B1F744EF468","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Coloring perfect \\((K 4\\)-e)-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Coloring_perfect_%5C((K_4%5C)-e)-free_graphs"}}}}}