{"entities":{"Q855256":{"pageid":857104,"ns":120,"title":"Item:Q855256","lastrevid":57181851,"modified":"2026-03-27T09:50:05Z","type":"item","id":"Q855256","labels":{"en":{"language":"en","value":"The strong perfect graph theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5081753"}},"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":"Q855256$A4F490A8-3306-4FDB-861D-EAD3910EAB72","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"90ba926b6241adcd3d5bf1c0a12d00a1cab727d6","datavalue":{"value":{"text":"The strong perfect graph theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q855256$63A73B3C-F00D-4C34-AC65-9FF28A6AC49F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ccf40e9f1be15e2418223608ddc3c334f1718a53","datavalue":{"value":"1112.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q855256$54244B94-CF4C-4C3B-AFB2-8696B71FB1D4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86791d2de8f741697c1a28c841b5e520b1ea6f17","datavalue":{"value":{"entity-type":"item","numeric-id":256974,"id":"Q256974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q855256$274A5403-2794-4504-BE38-90E01654BC87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fdbfdb659d9aeba37340367b24592700a75b41ee","datavalue":{"value":{"entity-type":"item","numeric-id":175487,"id":"Q175487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q855256$FBDB9A50-C1F3-4CEC-BD12-614AE80D29AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q855256$6A34B109-FB43-44A1-BAAA-DBE409A42227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c767c73643f6f9c229d2e29427c218355d7fa9cd","datavalue":{"value":{"entity-type":"item","numeric-id":186136,"id":"Q186136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q855256$EFFD9B1A-FCF6-48F7-B755-D50AEA8E97DB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"553c7ad508f4615999d4ef926cfdf75d436f510c","datavalue":{"value":{"entity-type":"item","numeric-id":175062,"id":"Q175062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q855256$3AA85967-3A4C-43BA-A763-19DA84F3D370","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"27b4e4a51bf604d70e174840a6623a8922651fb0","datavalue":{"value":{"time":"+2007-01-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":"Q855256$B9A5393D-8F74-42F4-BB28-29E20D37D141","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"be7efee2d613360598391063cde8f21454e796e9","datavalue":{"value":"https://arxiv.org/abs/math/0212070","type":"string"},"datatype":"url"},"type":"statement","id":"Q855256$3445B365-CC06-4EA1-BC24-266598044032","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f25b10bb870a274ba9042ea023d2344d99ec15b3","datavalue":{"value":"A graph \\(G\\) is perfect if, for every induced subgraph \\(H\\) of \\(G\\), the chromatic number of \\(H\\) equals the order of the largest complete subgraph of \\(H\\). A graph \\(G\\) is Berge if no induced subgraph of \\(G\\) is either an odd cycle of length five or more or the complement of such a graph. The study of these graphs was begun by \\textit{C. Berge} in 1961 [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10, 114 (1961)], in connection with a problem in information theory (the ``Shannon capacity'' of a graph lies between the clique number and the chromatic number, so for a perfect graph it equals both). Berge made two famous conjectures: (1) The complement of a perfect graph is perfect; and (2) A graph is perfect if and only if it is Berge. Since (2) implies (1), these are known as the strong perfect graph conjecture (2) and the weak perfect graph conjecture (1). \\textit{L. Lov\u00e1sz} proved (1) in 1972 [J. Comb. Theory, Ser. B 13, 95--98 (1972; Zbl 0241.05107)]. Much attention has been given to (2) in the intervening four decades, and a proof is given in the present paper.   A conjecture even stronger than (2) was made by \\textit{M. Conforti}, \\textit{G. Cornu\u00e9jols} and \\textit{K. Vuskovic} in 2004 [J. Comb. Theory, Ser. B 90, No. 2, 257--307 (2004; Zbl 1033.05047)], namely that every Berge graph either falls into one of a few basic classes, or admits one of a few kinds of separation (designed so that a minimum counterexample to (2) cannot have either of these properties). In the present paper, the authors prove this conjecture also.","type":"string"},"datatype":"string"},"type":"statement","id":"Q855256$BFAA44A9-6B15-4B36-9724-26EFC67BAB8D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q855256$B05D5175-F648-49B4-BCF4-CAAEA2A9CD10","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6ed74ed354719018a4ed2729b6f5b1318d990456","datavalue":{"value":"5081753","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q855256$51660FB6-84F4-4682-AA88-7C9B37F5C24E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q855256$34AFE569-4080-4BE7-AD1A-EB25DF10A518","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c5fdb9726c27f198566caa50baa2263e4c4ae0a3","datavalue":{"value":"Q29028413","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q855256$EF7A31FB-F6C1-4F8C-97A2-05FABC58F68E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"205b6d05d63e09819854956633396177079e7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":591987,"id":"Q591987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q855256$D55B30A5-379D-4DC2-8CC9-ED9773F12DF4","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":"Q855256$34A64D1D-227B-4814-AE49-7AD3EDD65264","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6105026e116a2e218a04073732ceb60a290570ba","datavalue":{"value":"W1973199140","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q855256$BD99D472-5C3F-4FA8-A230-0F53FE61450D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a9e305dccfe4f8a9d200a849f8c7858e362621b4","datavalue":{"value":"10.4007/ANNALS.2006.164.51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q855256$AB932E0E-9BBD-4920-8507-27316697AE30","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2d21640342dea187959c17afd4991149227b90c","datavalue":{"value":{"entity-type":"item","numeric-id":3798700,"id":"Q3798700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3f0116a9ab5140789943b6790a836aad10fe0cf","datavalue":{"value":{"amount":"+0.8455893","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q855256$E22EA0D2-310A-468F-9706-313DE5C046F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c10d26e208155c255e7ae7177c2f8567c1cd9b98","datavalue":{"value":{"entity-type":"item","numeric-id":686172,"id":"Q686172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aedc5c156257e786230b1401add0f9f79a0209b","datavalue":{"value":{"amount":"+0.8424907","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q855256$2C1F6670-CC9F-4459-B25D-C66A0C68FB7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84c86f631a9b0d0db7d889d026824b076b300877","datavalue":{"value":{"entity-type":"item","numeric-id":4549225,"id":"Q4549225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d6d9898f09bbad06f5d5d799f662817a5f681e1","datavalue":{"value":{"amount":"+0.83838695","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q855256$10ED0A6D-2BB2-464C-819B-556012997B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"892eafb07e69706c0f9e30bd9a85059cda0c982e","datavalue":{"value":{"entity-type":"item","numeric-id":1403295,"id":"Q1403295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f9125f9d0341f0c5308f015a7b9b12013dd63ea","datavalue":{"value":{"amount":"+0.83686686","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q855256$061A3E4B-334E-41CB-9F4D-F476664E076C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74a5efd0ade566877d97b34c730ed966580db288","datavalue":{"value":{"entity-type":"item","numeric-id":5487777,"id":"Q5487777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e0c12b058b20592fae15c6114fdc057923f8eee","datavalue":{"value":{"amount":"+0.82825816","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q855256$25474C72-2258-407C-8D38-DFEA0528D326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d51ceea08906828940b6b17745e46abf851e771c","datavalue":{"value":{"entity-type":"item","numeric-id":4798118,"id":"Q4798118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9240a3ff4e849f813871e658ffb3feb9a171e20e","datavalue":{"value":{"amount":"+0.819912","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q855256$026A7DF8-88ED-4634-83B4-BDCB27C61ED8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0485d0b87d7ef13b5d068e442cc095a0de88c6a5","datavalue":{"value":{"entity-type":"item","numeric-id":1121920,"id":"Q1121920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0303711f23a1fe314274a0d7a10b6809635f4a77","datavalue":{"value":{"amount":"+0.81914294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q855256$DC4C9626-085D-4516-B605-2A8A930FEF4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4add5281769213f2043556c93c255714beedfd3","datavalue":{"value":{"entity-type":"item","numeric-id":1112847,"id":"Q1112847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce56e9c076b62c5929ad908c317a143a59d0b065","datavalue":{"value":{"amount":"+0.81769013","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q855256$52AF98DA-753A-42E8-8BC1-C25CA726432F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33ce9d6c638e95d77fa3cc83f6b51b227ee42cc4","datavalue":{"value":{"entity-type":"item","numeric-id":2433714,"id":"Q2433714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f453d6012faee162791e72599a43d40e6503a128","datavalue":{"value":{"amount":"+0.814598","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q855256$E1FAB853-AA4A-4EEF-938E-A8B5E1CF6318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"704446db44961a061e5e703a4a9309e885d81b4a","datavalue":{"value":{"entity-type":"item","numeric-id":2822594,"id":"Q2822594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08c4b84b56c16d35b9d34c142e081311432e7a1f","datavalue":{"value":{"amount":"+0.80591786","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q855256$8586DDB1-A51D-4823-B232-41470CC26D48","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:855256","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:855256"}}}}}