{"entities":{"Q1332433":{"pageid":1343178,"ns":120,"title":"Item:Q1332433","lastrevid":46278903,"modified":"2025-12-24T11:35:47Z","type":"item","id":"Q1332433","labels":{"en":{"language":"en","value":"New classes of Berge perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 626353"}},"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":"Q1332433$276B6FFD-DC57-4C45-BEE7-2FCB1F6773A6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6d6a5b82db3f5331af4c07ea0cb4402347e23811","datavalue":{"value":{"text":"New classes of Berge perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1332433$68953FAF-C909-4551-857A-15FC188AFB50","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"43ead4e6149ff70a67e74dc8826aa89726fbd1f8","datavalue":{"value":"0807.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332433$6135CA36-E0F1-429C-82A5-C8CDE392FCD6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6136eb755e12ac9038e016fcfabf5ea4335696a5","datavalue":{"value":"10.1016/0012-365X(94)90373-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332433$657D9359-2DF0-47E8-9170-0D055166F7DD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"04e71569b0ebdef8629fef55e83176d19ee5910a","datavalue":{"value":{"entity-type":"item","numeric-id":849136,"id":"Q849136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$5C134C7D-D0A3-48FB-9799-2CB7BA32D7D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"42b3be3fd84ab4e46e98f17275cc4a0c654521b5","datavalue":{"value":{"entity-type":"item","numeric-id":185365,"id":"Q185365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$8FCB2A1F-2F39-49B7-AB1A-3C4AD7FE3AAE","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":"Q1332433$81C8CBA7-C341-42B1-AF44-FC0C696ECBA4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"65580a53a719086581e27570758e1a930bee1e54","datavalue":{"value":{"time":"+1995-02-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1332433$C57A380B-1FA2-40DA-8249-164F8F6FA5F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dae4e27cf4e145b4c38947464d0a9ae5b062303d","datavalue":{"value":"Chv\u00e1tal proved the star-cutset lemma saying that no maximal imperfect graph has a star-cutset. Using a notion of reducible clique and a special type of derived graph \\(G| K\\) (for a set \\(K\\subset V)\\), \\textit{A. Sassano} [Reducible cliques and the strong perfect graph conjecture, IASI Tech. Report R 257 (1989)] proved the following: If \\(\\mathcal G\\) is a hereditary class of Berge graphs in which each minimal imperfect graph \\(G\\) has a reducible clique \\(K\\) of size \\(\\omega(G)\\) such that \\(G| K\\) is also in \\(\\mathcal G\\), then every graph in \\(\\mathcal G\\) is perfect. In this paper, the authors prove that if \\(e\\) is an edge not belonging to any triangle of a minimal imperfect Berge graph \\(G\\), then \\(G-e\\) is also a minimal imperfect Berge graph.   The authors prove four classes of Berge graphs to be perfect: The chair is a graph with vertices \\(a\\), \\(b\\), \\(c\\), \\(d\\), \\(e\\) and edges \\(ab\\), \\(bc\\), \\(cd\\), \\(be\\). The graph \\(F_ 2\\) is obtained from a triangle by attaching a \\(P_ 2\\) at one vertex and a \\(P_ 3\\) at another vertex (or has vertices \\(a\\), \\(b\\), \\(c\\), \\(d\\), \\(e\\), \\(f\\) and edges \\(ab\\), \\(bc\\), \\(ca\\), \\(ad\\), \\(be\\), \\(ef\\)). \\(G_ 0\\) is the graph \\(P_ 4\\cup K_ 1\\) and \\(G_ 1\\) is obtained from a diamond by attaching a pendant edge at a vertex of degree 2. \\(H\\) is the graph \\(C_ 4\\cup K_ 1\\). Result 1: Every chair-free and \\(F_ 2\\)-free Berge graph is perfect. Result 2: Every \\(P_ 5\\)-free and \\(K_{2,3}\\)-free Berge graph is perfect. Result 4: Every \\(G_ 0\\)-free and \\(G_ 1\\)-free Berge graph is perfect. Result 5: Every \\(\\overline C_ 4\\)-free and \\(H\\)-free Berge graph is perfect.   The first two are proved using the star-cutset lemma, the third using Sassano's result and the fourth using the authors' result quoted above. All but one of the above classes of graphs are \\(\\overline C_ 4\\)-free. Thus considerable progress is achieved towards proving \\(\\overline C_ 4\\)-free Berge graphs to be perfect.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1332433$DF077C8A-EDD7-4B06-833F-4AA6C7952FA7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332433$2503593A-2D95-4702-B209-5C3914F8132C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"defcca056a0fe3be0f3631c352814ce84b43a5ba","datavalue":{"value":"626353","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332433$50C6A671-DF5F-45FF-8228-D9837091827B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1332433$6B6E6771-DDAE-4F55-8D89-3A5EF39E0621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cea499cfcd19a920ac5739c9837ec751c94289a","datavalue":{"value":"star-cutset lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q1332433$A0DBE159-5411-4050-A9EB-C6856E671B7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e07a04a5d7e2c38477db20cc1f929e07d2b28b0","datavalue":{"value":"imperfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1332433$9CC6A5F9-82CA-4374-9B36-949D09B8FAE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"622d0d5312dc4c8a1c5530df169c87a6332e493a","datavalue":{"value":"reducible clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1332433$72946159-D11F-494E-A11F-6F4D638451A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"383f8c40d49a3ae166580a1595836f3292bc52b8","datavalue":{"value":"Berge graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1332433$B7423C3C-4F95-42A0-B2A4-36A9E3CCE7A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03085a9ea63c13ca51766e21e0c9407a1b71184b","datavalue":{"value":"chair","type":"string"},"datatype":"string"},"type":"statement","id":"Q1332433$F6AC9932-6363-4D9D-9947-60D8DF267B92","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":"Q1332433$B980A5D8-2E19-4878-B614-14D1808365A9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$8E460D88-0798-4E24-9AFF-35671C0B5EE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8a74f042ba1f29a12a670ab9d659cf777707121","datavalue":{"value":{"entity-type":"item","numeric-id":798301,"id":"Q798301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$9BB65C07-756D-4157-99F6-FD14C9AC7948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$26B5C5B5-CB57-4F6E-9AF9-00C290CC4029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"377fc7d6f0f87cd999526d782ba240d822d49abd","datavalue":{"value":{"entity-type":"item","numeric-id":1121289,"id":"Q1121289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$C0AE7D8F-68C8-4C0C-9B7D-8B19786054A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6158b50eeb07f11af0caa758cb3e8ea0fab5c43e","datavalue":{"value":{"entity-type":"item","numeric-id":2366214,"id":"Q2366214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$876493C2-7CFF-4056-B2F9-5F1BFC722B6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddbe097f62791bcc42fe71dd30e6b393e0a8c6f9","datavalue":{"value":{"entity-type":"item","numeric-id":2553445,"id":"Q2553445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$95C1D035-DAE7-4B8F-916F-A2ADF1AAE855","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":"Q1332433$734709EF-244E-4270-9EB4-7F260F926FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f961bf9adafa4b952e8a82c014ce4d13792224fe","datavalue":{"value":{"entity-type":"item","numeric-id":1107542,"id":"Q1107542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$C9E6C3DA-9DC0-4A49-8FEC-FF34404E85C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c84f34fa167f28768d0f1d12588778fb1f4ffd19","datavalue":{"value":{"entity-type":"item","numeric-id":5903942,"id":"Q5903942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$E7BEFC6A-9B4A-467D-B9AE-4B46B080CC3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11c607b0c6f7409cf390c5742731d5c7cfd460f5","datavalue":{"value":{"entity-type":"item","numeric-id":4770779,"id":"Q4770779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$CB473B09-38BB-41A7-93E0-3E84E3734103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46cea1204e8b56e8cdf89cf3b32e1a95f1f87fb2","datavalue":{"value":{"entity-type":"item","numeric-id":1213881,"id":"Q1213881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$D59FA494-1C08-4641-9F19-0D621E959B48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b05636f797e670c0b724b22e9db1e87e8fe2110b","datavalue":{"value":{"entity-type":"item","numeric-id":1245851,"id":"Q1245851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332433$75B57186-FB82-4552-9DC4-72201DD33304","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9137158d8c356172906c7e0383fdc1f84f6af18f","datavalue":{"value":"https://doi.org/10.1016/0012-365x(94)90373-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1332433$14DBA766-C89A-4AA4-ADA1-79DFDF0BADAA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b2348807cd9b9965a443fc23761912cc97a7f323","datavalue":{"value":"W2068477628","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332433$B216EFB2-D511-4782-A578-AF824224CB04","rank":"normal"}],"P1643":[{"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":"0100d2c5ea57f0445715d811c4c73cb91498abc4","datavalue":{"value":{"amount":"+0.8408793807029724","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":"Q1332433$60AE765A-D7DB-4519-9473-642F91255D3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78423da174c95bb83b30d08df269b239d6725fd6","datavalue":{"value":{"entity-type":"item","numeric-id":1376074,"id":"Q1376074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9c9007045b141e9343bf3dd89127e421898139d","datavalue":{"value":{"amount":"+0.8388425707817078","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":"Q1332433$674DAF93-468E-4DAC-A242-CB3B8081BCA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7afe8944286952462b440ed5e551ef94ffd9aedb","datavalue":{"value":{"entity-type":"item","numeric-id":879162,"id":"Q879162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbd32bad7292d31cfb2c75bef888d69fc24341bb","datavalue":{"value":{"amount":"+0.828294575214386","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":"Q1332433$AF67A148-D798-4A80-AE37-F472061D284F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d3a2585cce289f0e08f8d0fc283c0ed27e1ad2a","datavalue":{"value":{"entity-type":"item","numeric-id":1095938,"id":"Q1095938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8949ee2bc8296eb2aad18d4655d0d514e6f4d63","datavalue":{"value":{"amount":"+0.827862024307251","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":"Q1332433$600C9015-57A3-49CD-A4D8-72999BF5E62E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1332433","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1332433"}}}}}