{"entities":{"Q2758337":{"pageid":2769076,"ns":120,"title":"Item:Q2758337","lastrevid":41978789,"modified":"2025-05-20T10:57:20Z","type":"item","id":"Q2758337","labels":{"en":{"language":"en","value":"Cutsets in perfect and minimal imperfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1679721"}},"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":"Q2758337$3FB44039-F42B-47A0-B2BF-053D626B6A59","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"52a9b0de7467f1688235f8b6530f6e7e2457cb23","datavalue":{"value":"0984.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758337$02A08A5E-87B5-4847-9D9A-DC98EF3AA5F0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3d173afbda7d364ee20fa0af1c6602b56374da2","datavalue":{"value":{"entity-type":"item","numeric-id":187141,"id":"Q187141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758337$B0DB8B66-8674-41C6-89C9-ACB5786657CF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e051b790077972112028dcca803b5e67c70fecd7","datavalue":{"value":{"time":"+2002-05-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2758337$2697027E-3AED-42A6-A52C-B275A34F934B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758337$81BDBE1F-691D-4C72-8E17-84E2403E8593","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758337$DB42CD9F-7AAE-4BC8-89F9-24EC7FE96B7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758337$9AA90424-4893-4960-A917-173A6D601097","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1e2ef1fa6b6c4cc0a0adea443d579b2e4aa7954c","datavalue":{"value":"1679721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758337$ACC13F22-A601-40EB-AAA0-8C66B225D45F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c76755b40378012473301226340484cbbecd869","datavalue":{"value":"cutset","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758337$6583F0C1-3F4C-473F-922A-88DE489B8133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758337$369F9809-4E75-49DD-9446-A4BC09A902CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"317e4c475f9fd751514a900c0c61e22b87893c4c","datavalue":{"value":"minimal imperfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758337$3983C61D-388D-4518-A613-B9A776FF2F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"434f7a183610e9c92aa79ca04a3932250a4c5e99","datavalue":{"value":"bonding","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758337$55A69735-B037-42E3-B096-384E1F88410C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7727a2a78943e2944fa61d35689b16e4e324c74","datavalue":{"value":"predicate-closure","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758337$FD725424-298B-41BB-8F6E-C61E2957E63D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46c19c6ebf141a97c3f103dda366c8b880df7ecc","datavalue":{"value":"partitionable graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758337$E6477377-1DE6-464D-8145-403C00BFA1D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"688ba7ad35f2839c69e563bd862dee17c124ce6c","datavalue":{"value":"small transversal","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758337$FD7967E0-586B-403B-84E2-E0731115C871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50e647c07b5488686a83d5a885e50233eb323960","datavalue":{"value":"strong perfect hraph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758337$ED234CE0-18AB-48F6-9C12-F0959CAA2890","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":"Q2758337$442C7B9C-7778-416A-B6A5-8B11B7B93853","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23731cfe2074a7e47bc915bc55ab93ce1d140acd","datavalue":{"value":{"entity-type":"item","numeric-id":1322031,"id":"Q1322031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe19b980289ee27cdb775c96e5e5253486a2f69c","datavalue":{"value":{"amount":"+0.94582427","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2758337$47E1847A-DF98-4716-94B2-0F3189A6CC85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e066f29c8bac330c780492b2e36aa0251c5f79cc","datavalue":{"value":{"entity-type":"item","numeric-id":700371,"id":"Q700371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7d1f1f3ce7b652195c192d76fc12ec73326845f","datavalue":{"value":{"amount":"+0.9361148","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2758337$F35C8062-1327-4720-8B9A-57FB346A6277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c592b037e6d91831ee7970380f2871ead5063f23","datavalue":{"value":{"entity-type":"item","numeric-id":4291679,"id":"Q4291679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f2cb73234e013a9ecd8cbf914aabeb15d37fe44","datavalue":{"value":{"amount":"+0.9152188","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2758337$6E1CEF26-7B13-4D6B-A9DF-FA79A8EFB4A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d68eae5c722bdcfcb0a617ae2c79c20e095dcb3","datavalue":{"value":{"entity-type":"item","numeric-id":5959087,"id":"Q5959087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c54b3df35b8a539604fc54ba543d25db60004cd","datavalue":{"value":{"amount":"+0.91494286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2758337$39CB1927-595B-447C-909C-3EDE47D7AAF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1571a258e731be96a9fba582533e39de647821b","datavalue":{"value":{"entity-type":"item","numeric-id":3344017,"id":"Q3344017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58247aee3ff111eb7869a4be512383daba788d9a","datavalue":{"value":{"amount":"+0.91432357","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2758337$35BF2023-0F4C-45C5-9FA9-4A4673061888","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bbbded179dce0f28dedae76db66036c5c3d07f9","datavalue":{"value":{"entity-type":"item","numeric-id":1121289,"id":"Q1121289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a625cad83f0cf1ec3c2a826de966c14adb1455b0","datavalue":{"value":{"amount":"+0.9130926","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2758337$E622B828-E077-4842-9505-57EBC05B27B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e366a988fc4ea83c98c43262c1332864fa2aa4ca","datavalue":{"value":{"entity-type":"item","numeric-id":3429746,"id":"Q3429746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60dcc1f098ba1d68d59e3801a974df04902566a1","datavalue":{"value":{"amount":"+0.9108468","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2758337$055C4523-58D2-4E74-BF35-7142A6A57694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7471a5203c09b066f93344ea81c30103b3fbd7d4","datavalue":{"value":{"entity-type":"item","numeric-id":1582067,"id":"Q1582067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cca76e1a7afef72aac50e22b2296f10c83761bf","datavalue":{"value":{"amount":"+0.90448695","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2758337$89EF8BBC-D750-4BE8-AC07-6ACC37EF24DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc80f9a143b9e65c4440e1c1f76f97715e71a2d4","datavalue":{"value":{"entity-type":"item","numeric-id":4808642,"id":"Q4808642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55da41ac479f9c93a9fa047d4e03b3d2d8ae6408","datavalue":{"value":{"amount":"+0.89923173","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2758337$BA9FF173-F5D4-43F7-946E-CF739BEA7B1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ce5a46f5bd8ffef2b0b180a5bd28b18172a5242","datavalue":{"value":{"entity-type":"item","numeric-id":4652629,"id":"Q4652629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dedef6bbe496dab9caf283c39f23b216ddb72419","datavalue":{"value":{"amount":"+0.8992316","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2758337$8C917F55-A54A-4DE5-85AB-543652868DE1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"010df3120212b535d6913e9f575c25e22fd85aff","datavalue":{"value":{"text":"Cutsets in perfect and minimal imperfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2758337$E573A6C3-9DDE-4946-94DD-28A0316A85B6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e670a4b02140d9c5589ab3f4d0a5b5d6bed8e51c","datavalue":{"value":"In this eighth chapter of the book ``Perfect graphs'', the author surveys the results on cutsets in perfect and minimal imperfect graphs. The concept of \\(F\\)-bonding and the closure of a set of graphs under a predicate are employed to construct larger classes of perfect graphs. NEWLINENEWLINENEWLINEIf two graphs \\(G_1\\) and \\(G_2\\) have a graph \\(F\\) as an induced subgraph, the \\(F\\)-bonding of \\(G_1\\) and \\(G_2\\) is obtained by identifying the corresponding vertices of \\(F\\) in \\(G_1\\) and \\(G_2\\). The review starts with the observation that clique-bonding (when \\(F\\) is a clique) alone preserves perfection (in general) and the corollary that no MIG (minimal imperfect graph) can contain a clique cutset. Results of Tucker, Chv\u00e1tal and Cornu\u00e9joles-Reed on non-existence of a stable cutset, a star cutset, and a complete multipartite cutset (respectively) in MIGs (with suitable modifications) are reviewed. Chv\u00e1tal's conjecture that no MIG admits a skew partition, Olariu's result on partitionable cutsets and Ho\u00e0ng's partial result on the skew partition conjecture are also dealt with. NEWLINENEWLINENEWLINESection 4 starts with the definition of the closure \\(\\mathcal{G}^P\\) of a class of graphs \\(\\mathcal{G}\\) under a predicate \\(P\\) by the rules: (i) if \\(G\\in \\mathcal{G}\\), then \\(G\\in \\mathcal{G}^P\\); and (ii) if \\(G\\) satisfies \\(P\\) and if \\(G-v \\in \\mathcal{G}^P\\) for every vertex \\(v\\) in \\(G\\), then \\(G\\in \\mathcal{G}^P\\). NEWLINENEWLINENEWLINEObserving that if \\(\\mathcal{G}\\) is a class of perfect graphs and \\(P\\) is a property a MIG cannot have then every graph in \\(\\mathcal{G}^P\\) is also perfect, the author considers the following predicate cases: (1) * = \\(G\\) or \\(\\overline{G}\\) has a star cutset, (2) \\(\\pi\\) = \\(G\\) is either a clique or a stable set or \\(G\\) has a partitionable cutset, (3) \\(c=G\\) has a clique cutset, (4) \\(s=G\\) has a stable cutset, and reviews the results for several classes of perfect graphs obtained as included in \\(\\mathcal{G}^P\\) for different choices of \\(\\mathcal{G}\\). In particular \\(\\text{Triv}^\\pi\\) is the class of perfect graphs, where Triv is the class of graphs with at most two vertices. These take up Sections 4, 5 and 6. NEWLINENEWLINENEWLINESections 7 and 8 are devoted to an examination of the status of several conjectures related to the Strong Perfect Graph Conjecture (SPGC). These include the ones imposing conditions on Berge graphs \\(G\\) like: neither \\(G\\) nor \\(\\overline{G}\\) has a star cutset/a stable cutset/an even pair/an odd pair/a skew partition, and two conjectures of Seb\u00f6 which are together equivalent to the SPGC and attempt to bridge the gap between partitionable graphs and MIGs through the concept of a small transversal.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758337$FE4F2C5C-9CB4-4816-BC05-E0F7CFA0E679","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2758337","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2758337"}}}}}