{"entities":{"Q1924490":{"pageid":1935232,"ns":120,"title":"Item:Q1924490","lastrevid":69674442,"modified":"2026-04-13T08:37:56Z","type":"item","id":"Q1924490","labels":{"en":{"language":"en","value":"Minimal imperfect graphs: A simple approach"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 936871"}},"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":"Q1924490$943CFD9A-1F4D-4D84-8D39-FEB62BAC209C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"767000ba63dc05f4e0ceeb9849d27f45b308de4b","datavalue":{"value":{"text":"Minimal imperfect graphs: A simple approach","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1924490$20A66E2F-58FF-49B2-9A61-D4A5BA105EA3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9f81e05ebb76af6ac1a878ade1fdd46568cc51a7","datavalue":{"value":"0858.05044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924490$B41A23C8-E1B8-48CF-9E9C-5CB48CE5225B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"535c281e6c34710cf893228fdc3e880105608a07","datavalue":{"value":"10.1007/BF01844846","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924490$4FDD3F69-480D-4ABB-A6C7-B1455DAD31FF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec8d107a5c215bdfe36c0cc6c5e7a15a5273a391","datavalue":{"value":{"entity-type":"item","numeric-id":1924489,"id":"Q1924489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924490$70B8EA9B-1FB2-43F7-AF61-28F1398F8E4F","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":"Q1924490$CFA57FCC-EF8F-4FF1-A450-516B7F6298A3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7d08bb9a72a2259fe21464e6025b4a7e58a684cc","datavalue":{"value":{"time":"+1997-03-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":"Q1924490$F8CE0515-7E5B-4907-99FE-C2B882A660C0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1c79a1628147dd8ef8a90709e8cafbdff8d1f59b","datavalue":{"value":"For a graph \\(G\\), let \\(\\omega(G)\\) denote the cardinality of a maximum clique of \\(G\\), and \\(\\alpha(G)\\) the cardinality of a maximum independent set. \\textit{L. Lov\u00e1sz} [J. Comb. Theory, Ser. B 13, 95-98 (1972; Zbl 0241.05107)] showed that a graph \\(G\\) is perfect iff \\(|H|\\leq \\omega(H)\\alpha(H)\\) for every induced subgraph \\(H\\) of \\(G\\). This paper provides a short proof of this theorem, and discusses its consequences.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924490$40D00FE9-E76E-4B5A-B749-37D102C14E5E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a714b8b1c3541c6d37b111d53efd3e2dabb173f9","datavalue":{"value":{"entity-type":"item","numeric-id":1297762,"id":"Q1297762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924490$F332F147-5D24-4B3F-85DC-0C8E5411F2D5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924490$D2936DC0-1091-4F04-94CC-6F5BEC9BC285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924490$4F6ECAB7-2C90-437C-81D7-BDBAE3C126D7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"44a1e34272230813c1078f2a0c7ea0da89ae385e","datavalue":{"value":"936871","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924490$37BE75EB-C50B-45E9-8075-BC0057F8E7FE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924490$6E251532-7B09-4533-AEE7-D6EBFB3636C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924490$ADE6CDE2-42F9-4AD2-BCDE-03D1BBA45E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924490$4157091B-C278-40A5-A114-878B191B4A87","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":"Q1924490$05C18E7C-8131-4B32-BE6A-D6CB6F782B0A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d59fb568ab69c8d057b84e4ffc141366f119d24a","datavalue":{"value":{"entity-type":"item","numeric-id":1132889,"id":"Q1132889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924490$5BF649E3-5A8B-40A7-8C9C-42D505F69885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3ecc4ed854f4c2fb93ed2e8327283eb9cc15cf0","datavalue":{"value":{"entity-type":"item","numeric-id":1393418,"id":"Q1393418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924490$15055150-4C94-45E6-AF87-DC57AF739CF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ded27f1e83e96a67ea1d73bc07d2d5f5be56485","datavalue":{"value":{"entity-type":"item","numeric-id":5609153,"id":"Q5609153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924490$70D175CC-AC66-46BF-8A8A-1A4106726722","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":"Q1924490$C30DF861-36E6-4DBD-BDF9-A53EEB4FA25D","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":"Q1924490$6CD42992-EAB3-4C62-AE2D-2699753E3A82","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":"Q1924490$E149AE97-8C2F-491F-B951-0A48545C4147","rank":"normal"}],"P1643":[{"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":"fcbe2e59b0d5d3cd8c12d456b63d50df09db7259","datavalue":{"value":{"amount":"+0.8191680312156677","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":"Q1924490$DFA0BD9C-82AD-471C-91ED-44CF235AA55E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa06385a608fccd8488d4fdbcf0c23d33d05e497","datavalue":{"value":{"entity-type":"item","numeric-id":4300578,"id":"Q4300578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f15efa128bf4cb962f513add01bcbb9b2e84c7fc","datavalue":{"value":{"amount":"+0.805155336856842","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":"Q1924490$D726C9AD-3ABA-4C13-A1CC-4C9B57472BB9","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":"6c0c334b34b5d0fc981839db3e85e6d1da1cc8b1","datavalue":{"value":{"amount":"+0.803234338760376","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":"Q1924490$BF2E0D34-7E3F-4C1B-A21F-217EC667B497","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":"60158b0bdc908295a8fc06d21fea56ad519772c3","datavalue":{"value":{"amount":"+0.8015088438987732","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":"Q1924490$9BC3DA00-7EF6-4DAE-B8E9-70E586CB2971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e78b7c211f3f09e89c1220a2f57b85bed054f65","datavalue":{"value":{"entity-type":"item","numeric-id":1735702,"id":"Q1735702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0e05599add3c456cad7cf68b24de3bb4f1d4273","datavalue":{"value":{"amount":"+0.8006922006607056","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":"Q1924490$43E64679-A643-4A2B-9D93-9285FA09B56F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimal imperfect graphs: A simple approach","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimal_imperfect_graphs:_A_simple_approach"}}}}}