{"entities":{"Q879162":{"pageid":881010,"ns":120,"title":"Item:Q879162","lastrevid":42741287,"modified":"2025-07-09T18:12:50Z","type":"item","id":"Q879162","labels":{"en":{"language":"en","value":"Decomposing Berge graphs containing no proper wheel, long prism or their complements"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5150173"}},"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":"Q879162$B7BE4868-E248-4D3C-8F3B-200A7A9F81CC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7521de0d827850a4f19492d5bd2312f84a9180c6","datavalue":{"value":{"text":"Decomposing Berge graphs containing no proper wheel, long prism or their complements","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q879162$448D546D-F6C2-42A1-9885-DE091D5A9226","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"19c7855e5f40d32fa4ed637906bdd199c8040388","datavalue":{"value":"1121.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879162$5D00547D-96DD-4030-A253-C1EC1EF6D402","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c7321a603fe216fdb28b1f9438d44e28433bc753","datavalue":{"value":{"entity-type":"item","numeric-id":378134,"id":"Q378134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879162$9B904160-DBC5-4902-A652-34351649D041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa9a170b566faa650496c61eaa134019d05c6a23","datavalue":{"value":{"entity-type":"item","numeric-id":203960,"id":"Q203960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879162$4797B898-3E01-4DB6-82A8-8C033C313799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"feb07495fa8de76912d587852b3aa20404b344f1","datavalue":{"value":{"entity-type":"item","numeric-id":163019,"id":"Q163019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879162$37263338-AE21-4A1D-B1E7-77F2D6FFE13B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879162$EAFE84D7-9209-4136-91F9-555C3759CE89","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0ef68d2ac953bb6a5d4619876ccd47f691709c15","datavalue":{"value":{"time":"+2007-05-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q879162$2035CDFF-FD43-45E6-AD40-691FAAF1FDB0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0ae2d70e91cfb90bbdf4777f84599d63a8b48905","datavalue":{"value":"A graph is said to be perfect if, in all its induced subgraphs, the size of a largest clique is equal to the chromatic number and a graph is said to be Berge if it does not contain an odd hole or its complement. The strong perfect graph conjecture (SPGC) states that Berge graphs are perfect. In this paper it is shown that, if \\(G\\) is a Berge graph such that neither \\(G\\) nor its complement \\(\\overline{G}\\) contains certain induced subgraphs, named proper wheels and long prisms (described in the paper), then either \\(G\\) is a basic perfect graph (a bipartite graph, a line graph of a bipartite graph or the complement of such graphs) or it has a skew partition that cannot occur in a minimally imperfect graph. This structural result implies that \\(G\\) is perfect.   Note that this paper has been submitted in May 2002 and revised in November 2003 and \\textit{M. Chudnovsky, N. Robertson, P. Seymour} and \\textit{R. Thomas} simultaneously (June 2002) [Ann. Math. (2) 164, No. 1, 51--229 (2006; Zbl 1112.05042)] proved a similar result; finally they also showed that no minimally imperfect Berge graph satisfies the following property: \\(G\\) contains a proper wheel but neither \\(G\\) nor \\(\\overline{G}\\) contains a long prism, thus solving the SPGC.","type":"string"},"datatype":"string"},"type":"statement","id":"Q879162$F55A9027-933B-4BD2-AFB8-8FE1DB9E5FAE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879162$DE6F61A3-D2FB-48DC-A504-443FCA75E0FA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879162$489933D0-FE4C-48DA-BF74-C00C5D5045B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c427cabd2242d5a91b297dcd149e218db5178346","datavalue":{"value":"5150173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879162$E3D44545-6F99-4EE5-8657-A048C5A61D81","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5594bf089e20db614ce61dae32b887cd362d61e2","datavalue":{"value":"Berge graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q879162$8DED8F3E-3BEF-478D-BD3D-86BC3615E4E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q879162$A4FA048E-7F4E-4956-98A5-699DE7C5F8B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a11116a6b4821127d46d686f666f969b50e0a4e","datavalue":{"value":"strong perfect graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q879162$A3970E31-E8FE-4EB0-903F-196D0FE8565E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20fc117f41eff2b657ba23650115bb1f04cc8d7e","datavalue":{"value":"proper wheel","type":"string"},"datatype":"string"},"type":"statement","id":"Q879162$2E7A69E4-DE90-4DA8-B5E2-A6F865E7A902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b73321ad2e7385df3f49a9257258d30245abb177","datavalue":{"value":"long prism","type":"string"},"datatype":"string"},"type":"statement","id":"Q879162$4B9CBA4A-E59A-4F0F-AF16-4B56DECBE1E1","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":"Q879162$43BEDD9E-4EB1-47BE-A8BE-4B0356171D2E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bddc9424623767c3de9577a6c8cb8639d741b28b","datavalue":{"value":"https://doi.org/10.1007/s00493-006-0031-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q879162$D76C7975-3DB5-4613-B39A-101284A5B0AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e523b585f75f38242092343e5d68e09910142bc4","datavalue":{"value":"W2096164989","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879162$65CE02BC-BA43-406C-A55B-63444BA9AF91","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5a9348000b70a43936a71ab00a21d48398c7cc20","datavalue":{"value":"10.1007/S00493-006-0031-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879162$2FC5CFE4-E3D0-4039-A40D-E78A092668E4","rank":"normal"}],"P1643":[{"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":"1f3f1ad51868ef529bc0fba8d2a2dc5cafed4249","datavalue":{"value":{"amount":"+0.82084703","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":"Q879162$8755C7E0-7874-419D-A66C-5C1DCD4A0454","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":"8c9faf40e3e7b5d2745f1d0ec9566444e9ca7dd7","datavalue":{"value":{"amount":"+0.81724286","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":"Q879162$C109EC9B-A8A3-40D5-A6EC-BF91723B0349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0219261c33170d756b149ce0319bf5824298aeaf","datavalue":{"value":{"entity-type":"item","numeric-id":855256,"id":"Q855256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8faf5e49c534459f783a35b4f99abc0f0a782db6","datavalue":{"value":{"amount":"+0.8041997","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":"Q879162$FA60D8E3-D72E-4551-BC3A-E1269090925A","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":"40ea6465714ebca44628c0dea06282739182137c","datavalue":{"value":{"amount":"+0.79700446","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":"Q879162$1E9B7FF8-92A5-426D-9742-F07C1C155281","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":"c445d7c3637957f0502413d7ba846371ff99b393","datavalue":{"value":{"amount":"+0.78914773","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":"Q879162$E5C49CE5-9252-422B-9C0F-BC671BE36AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47a500ac22d9a454014678a2f68e14e6c609e21a","datavalue":{"value":{"entity-type":"item","numeric-id":3424772,"id":"Q3424772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7adf2012b81164feb3f6376fb93f7feea637687","datavalue":{"value":{"amount":"+0.7869705","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":"Q879162$FDE46191-66A4-43B7-8BEC-483D9BF0DB6F","rank":"normal"},{"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":"e39438fcf82ffc108c1d5b01aea09504456f4b86","datavalue":{"value":{"amount":"+0.7841557","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":"Q879162$8F931D87-8EF4-432B-BA6C-017C42D05F47","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":"c950d1cf91d1cb2d49b8abfe92a99ee3088bb5b1","datavalue":{"value":{"amount":"+0.78225243","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":"Q879162$49F57492-7E91-42B7-BD08-21DA950EEB1E","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":"5c710cecd086fa2b7760a85dd9be83708bef4d00","datavalue":{"value":{"amount":"+0.78177506","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":"Q879162$120A6687-A3BE-4B06-AF69-50E5A0BA7D29","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":"dd80a16b797ac8bdd8444a2cc6d2deea086f532e","datavalue":{"value":{"amount":"+0.7738196","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":"Q879162$E09CE2D8-16F4-48D1-8067-F0D1FE384B27","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:879162","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:879162"}}}}}