{"entities":{"Q2822594":{"pageid":2833332,"ns":120,"title":"Item:Q2822594","lastrevid":79425293,"modified":"2026-05-06T13:52:43Z","type":"item","id":"Q2822594","labels":{"en":{"language":"en","value":"Perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6632110"}},"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":"Q2822594$F63496D0-1EFD-4C2E-ACA8-4D2EE65FB09E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"830e1e737780bd1a16deb4d66b117acbb27a2f7e","datavalue":{"value":"1351.05094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2822594$7CB17509-D58C-442A-B1B7-6EB6DEC4021C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5560ccf859e7ec21722beff92f5465d154a667eb","datavalue":{"value":{"time":"+2016-09-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2822594$5F91C401-C075-4412-9D7B-D24B82599429","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2822594$3C77749D-C67C-46C2-A5F9-1157A8A48591","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2822594$2B735FDE-14C5-403C-B23F-3D1CB28E7C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2822594$7E7C5F88-261F-40BB-A34D-3857A5205FA4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a42088891da2e4ebcea8dcfa666db0ed9e64476b","datavalue":{"value":"6632110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2822594$21755E42-92DE-45E2-9504-3031863F4924","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2822594$7D564526-39C4-456B-BBD5-8CFEAFCFEAD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59e104fc9083dc8c4e491b340ba5128d82bfc9b1","datavalue":{"value":"colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2822594$8104E8BA-3110-47B3-A251-48CC0DE55831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e87bb1aed89f5da6ee5d1aa38eb687932a17c03","datavalue":{"value":"subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2822594$19607C9D-0BA3-4B6D-9D67-D69EDBC4CAAE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba8963bf07877ded4133836acba07ecf77a509c7","datavalue":{"value":{"entity-type":"item","numeric-id":442236,"id":"Q442236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2822594$783E5273-294E-4A3D-83E1-C6A1A0EB7899","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":"Q2822594$EE2A028D-1F92-4B34-95B7-FFE4E442EE96","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"34f9beb17a67c6d90fe1cd9c9331a388ff4081b9","datavalue":{"value":{"text":"Perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2822594$DB188482-F7E2-43BE-A8C7-EEC7353620AB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cf854268a3e579a40e32a998caeb3db8bfad37ea","datavalue":{"value":"From the author's introduction: ``Every graph \\(G\\) clearly satisfies \\(\\chi(G)\\geq\\omega(G)\\), where \\(\\omega(G)\\) is the clique number of \\(G\\), because the vertices of a clique must receive different colours. A graph \\(G\\) is perfect if every induced subgraph \\(H\\) of \\(G\\) satisfies \\(\\chi(H)=\\omega(H)\\). A chordless cycle of length \\(2k+1\\), for \\(k\\geq 2\\), satisfies \\(3=\\chi>\\omega=2\\), and its complement satisfies \\(k+1=\\chi>\\omega=k\\); these graphs are therefore imperfect. Since perfect graphs are closed under taking induced subgraphs, they must be defined by excluding a family \\(\\mathcal{F}\\) of graphs as induced subgraphs. The strong perfect graph theorem (SPGT for short) states that the two examples just given are the only members of \\(\\mathcal{F}\\).'' NEWLINENEWLINENEWLINE Perfect graphs were defined by \\textit{C. Berge} [``F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind'', [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 10, 114--115 (1961)]. This paper presents a survey about perfect graphs that mostly focuses on the SPGT.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2822594$63D7C840-5FDB-4AE8-A02A-3A7C15851C72","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ba3efcb7de77d1bd49142f0373b838a01109e4e7","datavalue":{"value":{"entity-type":"item","numeric-id":584284,"id":"Q584284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2822594$180BA526-2548-4427-A1C9-B207C4265D92","rank":"normal"}],"P1643":[{"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":"ca19b08a6575fbb07fbf7bd32c075061f9ecd750","datavalue":{"value":{"amount":"+0.8766860961914062","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":"Q2822594$2FDE4317-2442-4CCD-AE5E-B02791358836","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":"ca19b08a6575fbb07fbf7bd32c075061f9ecd750","datavalue":{"value":{"amount":"+0.8766860961914062","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":"Q2822594$F1661704-A714-4B6B-BE2C-B936D8B92CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fa303011353dedefdefdd44f491078358d4bf68","datavalue":{"value":{"entity-type":"item","numeric-id":3351379,"id":"Q3351379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3508f3d63278f983040be74bd325cd2dd7d9710","datavalue":{"value":{"amount":"+0.871671736240387","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":"Q2822594$D11D77C8-49BF-4CD5-8DF9-41B9392632CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc20b62cb9c6b85fbe0b1784833623ce37018561","datavalue":{"value":{"entity-type":"item","numeric-id":5903942,"id":"Q5903942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e07f1a44adebcf8be684aa92e5c01e186d39a9da","datavalue":{"value":{"amount":"+0.8712362051010132","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":"Q2822594$C5A5453A-26C9-4CAE-845C-0D4C5C3D8562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d8e53686dc801fb6def850de5a8249c2eaf65c4","datavalue":{"value":{"entity-type":"item","numeric-id":1084108,"id":"Q1084108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8369ac887155e6e05632c1d4e460ada6a95f59a6","datavalue":{"value":{"amount":"+0.8655791878700256","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":"Q2822594$8E013F7A-DDE5-4893-A265-04E5FB869E07","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Perfect graphs","badges":[]}}}}}