{"entities":{"Q686172":{"pageid":688021,"ns":120,"title":"Item:Q686172","lastrevid":63469590,"modified":"2026-04-11T13:22:49Z","type":"item","id":"Q686172","labels":{"en":{"language":"en","value":"Counterexamples to three conjectures concerning perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428011"}},"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":"Q686172$30C5E811-4009-44C2-9B4D-BE17E420B3B0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7c8bf55658a65bc915611d80f89e9a4c4e36d506","datavalue":{"value":{"text":"Counterexamples to three conjectures concerning perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686172$4D1B5F3A-E330-49CA-B772-82ED180136D3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cea067f4b3f013a8512bdc4e0960fad1a892d18c","datavalue":{"value":"0795.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686172$C737EBC2-851D-42F6-B8FC-A3274EBA02AB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"087fe26188dd44cd95de13449415884d251bb988","datavalue":{"value":"10.1016/0012-365X(93)90338-T","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686172$9EE03212-B5AA-4C23-A9DC-26062ED9D5CF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"62ff535d2ba7354e7303f2e291d7bfd613cdf256","datavalue":{"value":{"entity-type":"item","numeric-id":495036,"id":"Q495036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$A8735F0A-8F22-4ABB-8C73-985F0C8806FB","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":"Q686172$06F3F16B-42B3-4485-ABDA-6BC62922BB46","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4780992a512f8eae7da384a8eaf64ba6fb4b678a","datavalue":{"value":{"time":"+1994-09-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686172$BDD23ED6-A949-4C19-997E-FCCD6274508B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7f424de76fb2b0a6536e1ed5566c3d02d9394b47","datavalue":{"value":"A graph is perfect if and only if for every induced subgraph \\(H\\) of \\(G\\) the chromatic number of \\(H\\) equals the size of a largest clique in \\(H\\). A graph is called Berge if neither \\(G\\) nor its complement contains an odd- length induced cycle of length greater than 3. The famous Strong Perfect Graph Conjecture states: A graph is perfect if and only if it is Berge. In search of a proof of this conjecture a large theory has developed and many related conjectures made. This paper represents counterexamples to three such conjectures, all somewhat technical. A graph is minimal imperfect if it is not perfect but all proper induced subgraph are perfect. An even pair in \\(G\\) is a pair of vertices such that all induced paths between them have even length. One of the conjectures is: If a graph contains an even pair then it has an even pair at distance two. If this conjecture were true, the strong perfect graph conjecture would follow. Another disproven conjecture is: Every Berge graph or its complement contains an even pair or a star-cutset or is the line graph of a bipartite graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686172$AE697563-0493-4A90-9E94-7635BDF8FECA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686172$BEEA2EE6-D4FC-4A28-8DFE-6B27FB85E4C0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"93da72b9545daa602378bbdc78207fe81d1efd67","datavalue":{"value":"428011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686172$0E1EDF09-686C-49E6-BA4A-DCF63888AC5D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a11116a6b4821127d46d686f666f969b50e0a4e","datavalue":{"value":"strong perfect graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q686172$5ED06185-0467-4CD7-B1B4-E82D7AF27891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q686172$DC7D956C-838B-4F36-B63B-71EB41B0C5ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5594bf089e20db614ce61dae32b887cd362d61e2","datavalue":{"value":"Berge graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q686172$83900659-A4C7-45AE-AD9A-B2E3793C5425","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1036338e57ff468c07842b36de9d1ae094bc8bd2","datavalue":{"value":{"entity-type":"item","numeric-id":1110542,"id":"Q1110542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$C228D8B6-42FF-496C-B59E-A1BEB31D296A","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":"Q686172$63D1DECF-12DE-4EC9-95E1-668402DCD915","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7995735646af3f1cf7c996fa68ca3a54f953d9b4","datavalue":{"value":"Q123252948","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686172$F40FE519-80F1-4F23-9E59-3F17D83695AA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"22ad8c0cf8959fb3be24778fa28798afcfd7af02","datavalue":{"value":{"entity-type":"item","numeric-id":3286847,"id":"Q3286847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$FDD6AED9-AD63-4D9F-ACBB-1BCBBCC2EFF1","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":"Q686172$F4387C3A-7E3E-4F88-8006-760ECC4CCF3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe62b841b14fce3b2eb1a6410c503c89c3ac7b59","datavalue":{"value":{"entity-type":"item","numeric-id":3967551,"id":"Q3967551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$B2656C40-FA86-44C0-AC5F-CC1FB16897CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78fcefc7eb6db493b1640335979e0e48c2971f01","datavalue":{"value":{"entity-type":"item","numeric-id":3291037,"id":"Q3291037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$38ECF7CE-995E-4D0F-BE84-522E1C88B0CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab623b16ab84aead0607079066242cc0c47d3981","datavalue":{"value":{"entity-type":"item","numeric-id":1813714,"id":"Q1813714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$E3FE910E-A2C3-41AC-8444-023027A49755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e937c6906c8b86060c65586b150f2d1d3a9425ac","datavalue":{"value":{"entity-type":"item","numeric-id":1111563,"id":"Q1111563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$0716C25B-17E3-4843-83FC-D7827579B477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"493b9c7b82f10ace40363dca412120e379dc666c","datavalue":{"value":{"entity-type":"item","numeric-id":1095159,"id":"Q1095159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$7218F082-4C32-4820-8A3B-443D51673632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d805d39c87d3dd9dd3ce670f5624942a5527159","datavalue":{"value":{"entity-type":"item","numeric-id":1089007,"id":"Q1089007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$75D5C412-1B26-46C5-AD9B-F4284274B1A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d709e0561ce1b036177950c6829a3bd690f6098","datavalue":{"value":{"entity-type":"item","numeric-id":4103550,"id":"Q4103550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$394898EB-90AB-46C2-AF29-FCFF6BD05024","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":"Q686172$64CB9B84-EE83-43D7-9E8D-D149E2EB47FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f14929504188a53ef660023bd30753f8781f60c","datavalue":{"value":{"entity-type":"item","numeric-id":1104342,"id":"Q1104342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$522BC0FA-F3B2-4ABF-B67C-6305061304B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"003e705696fa531074d13a48bf6b4645a2e8625e","datavalue":{"value":{"entity-type":"item","numeric-id":1104341,"id":"Q1104341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$5274B7DF-0D19-4544-9F32-FE26711B0E43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d12752e7e3b87a1df82f1629f2c888413b32ca16","datavalue":{"value":{"entity-type":"item","numeric-id":1071025,"id":"Q1071025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686172$89F3AF2B-A1C4-4406-BA8E-FCC2D94E0BFE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce904569b2f60ab00ce52d9eb9869797b8e5094e","datavalue":{"value":{"entity-type":"item","numeric-id":4522468,"id":"Q4522468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d7ca91c711b687a165a19d85f17d9d3e152e880","datavalue":{"value":{"amount":"+0.928235","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":"Q686172$0BBA0A0F-B5E7-4430-9BC9-84C054B2D4C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95fedf6fe08921d93c9ef62d0dd3fd93a3040979","datavalue":{"value":{"entity-type":"item","numeric-id":1248633,"id":"Q1248633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c5b42c966d7a19b9434a70d39b265d7163b7651","datavalue":{"value":{"amount":"+0.90537524","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":"Q686172$4A585705-7D42-403B-801A-BF35C192130F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f790705665dbfe95044adfb9eadeb916cb7e50a0","datavalue":{"value":{"entity-type":"item","numeric-id":1850071,"id":"Q1850071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cab368aa415e8af0bb2e6bddc96f7c2d3d47d35","datavalue":{"value":{"amount":"+0.90343285","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":"Q686172$BB0BF6B6-D3F3-4D54-A6FB-93DD0AC7BC9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33341ceba066eb9fe47bf52d97827188f5eda5ba","datavalue":{"value":{"entity-type":"item","numeric-id":5046003,"id":"Q5046003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7815364a257261007b92844414181148556c7909","datavalue":{"value":{"amount":"+0.9002953","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":"Q686172$37CF5A99-15BD-49F1-A315-FF1CA5111B02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f311fcb7780dc0ee737c08017cd6eafe73d2e73","datavalue":{"value":{"entity-type":"item","numeric-id":2449569,"id":"Q2449569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cab8e0e453a984a426b328b48524d7c57d1779a7","datavalue":{"value":{"amount":"+0.8965564","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":"Q686172$8D187F2F-CD34-4E8C-9ED5-F3C97AA009AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63379e1720e3df6603e8145fd963d000db4920f7","datavalue":{"value":{"entity-type":"item","numeric-id":3680854,"id":"Q3680854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4aae43e17f4db293f8736e1f02b7cefe1feb1dd","datavalue":{"value":{"amount":"+0.89603734","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":"Q686172$0356B517-0780-494C-AF90-2CBEE5FC776C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ed1746aa4513572db473534847263dd01ed8fb0","datavalue":{"value":{"entity-type":"item","numeric-id":4798120,"id":"Q4798120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84135d6a4b1f8c1f6ec9ac66bf8cdffff168f297","datavalue":{"value":{"amount":"+0.8936451","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":"Q686172$8B48A53E-19D4-4DAA-BC4F-AF7589F892C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3423bddf8b09b2f51b437879263ddca2211f87b6","datavalue":{"value":{"entity-type":"item","numeric-id":2978190,"id":"Q2978190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11965dd72deb482370cac72b45f9228d9b974895","datavalue":{"value":{"amount":"+0.8907405","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":"Q686172$561FB103-6292-4151-8B69-80527C046DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f063e869023d81ea48f1e683b98bbd2e2a9b04d5","datavalue":{"value":{"entity-type":"item","numeric-id":3222224,"id":"Q3222224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9a6094bdec02eaeef2845ff9fad91f6f9436642","datavalue":{"value":{"amount":"+0.88932997","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":"Q686172$C91EBC32-63F5-4ED3-85BD-567825F0ACC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efafcf5ffc31f3bc433d2e5d5125e9273ad5e2fe","datavalue":{"value":{"entity-type":"item","numeric-id":2053720,"id":"Q2053720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba434e8b0a14e2bccc70ae0e0ddac1163ada7bc2","datavalue":{"value":{"amount":"+0.88467914","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":"Q686172$A607F1B9-2118-4812-9E77-BE0558D4CA27","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Counterexamples to three conjectures concerning perfect graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Counterexamples_to_three_conjectures_concerning_perfect_graphs"}}}}}