{"entities":{"Q1084108":{"pageid":1094860,"ns":120,"title":"Item:Q1084108","lastrevid":66698541,"modified":"2026-04-12T12:11:36Z","type":"item","id":"Q1084108","labels":{"en":{"language":"en","value":"A note on perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3977026"}},"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":"Q1084108$59211DB0-B749-4E9E-A856-ABEC0BC02DC6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3d4d080fac7a9e9d1d9042d386d886d906ae1e4b","datavalue":{"value":{"text":"A note on perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1084108$C3B3E39D-2096-44BE-AFD8-D81EFEDA5570","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"319f76106baa9413f3ac74b8580f2c32f118feb9","datavalue":{"value":"0605.05014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084108$5DC7633B-8988-46B1-AD8D-42606F4050A7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d2d0af3c427756c3f9bd427052c5e959ac27c82f","datavalue":{"value":"10.1007/BF01848646","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084108$DAF1A113-EC4A-4195-B7C3-D2A896CF4D87","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3b8576669bc0ecd8cf391048775047cac1b4b93","datavalue":{"value":{"entity-type":"item","numeric-id":168646,"id":"Q168646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084108$2DD9584D-2FF2-4A6D-BAB7-E8612D22D3B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8dbc842d5eaf927385a86766f1454e06a1c019ee","datavalue":{"value":{"entity-type":"item","numeric-id":204137,"id":"Q204137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084108$AB96F5A8-A819-406C-8404-A32F47CCABCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"201364cbbc61e0d0a85431778d2e1c2e76306b69","datavalue":{"value":{"entity-type":"item","numeric-id":6480584,"id":"Q6480584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084108$8496CA54-1852-461E-9BEB-54C1788B8E76","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"615950119797f35f49728e278e9727b73c5c7f8e","datavalue":{"value":{"entity-type":"item","numeric-id":168620,"id":"Q168620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084108$EDCFECA2-9FA7-4EAA-B74B-974D9C5C93D8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1084108$B4083536-3902-48BB-A73D-6E0C24044B34","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9cb414748d581421b2f3901016fdd8d9e858be7c","datavalue":{"value":"A simple graph G is called perfect if every induced subgraph G' of G satisfies \\(\\chi (G')=\\omega (G')\\), where X(G') is the chromatic number and \\(\\omega\\) (G') is the size of a maximum clique of G'.    \\textit{L. Lov\u00e1sz} had shown that the complement of a perfect is perfect [Discrete Math. 2, 253-267 (1972; Zbl 0239.05111)]. The following generalization is proved here. Let the lines of a complete graph be \\(\\gamma\\)-colored with colors red, green and black, so that no triangle gets all three colors. Suppose that the two graphs formed by the red lines and green lines, respectively, are perfect. Then so is the graph formed by the black lines. It is then conjectured that the hypothesis can be weakened in a specific way.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084108$BFA05A9B-5419-4475-9DA7-55068DEB09EE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084108$E355476B-5E88-4167-BE02-F571701B2ED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084108$50637213-FE95-409A-9C70-11C54ADEF945","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"13dd41404d9dac8a29b72d7c72149e64fc5191f7","datavalue":{"value":"3977026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084108$032B7F08-8E73-4844-B25C-0C61708E29E0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9295a9222f526a12d4390138dae7356bf7f53e36","datavalue":{"value":"line colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084108$8A4575BE-FAC7-42B6-AA4C-3EC054614D0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e3d58b5f68ae7d6337620e7d25da0081273ed23","datavalue":{"value":"edge colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084108$1FD40558-BC92-469E-8317-5AA45399499D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084108$0777ED1B-981C-4473-89CE-5E38490F4A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f2bd7369831d9e54b4e511b9d71ba97d1e383ac","datavalue":{"value":"complete graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084108$FC25B7BB-64D9-479E-BC04-D51104798015","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"6d7128873961aaefc1b4cd5f4ae8bef8df36bbb7","datavalue":{"value":"Q56388176","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084108$C24950E9-B5F2-4582-AB82-58B2BA281AAF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4160ba73cc613e2769e008ae8a9ce69c96d8603f","datavalue":{"value":{"entity-type":"item","numeric-id":207053,"id":"Q207053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084108$308B83EF-A1B6-49E9-9BAB-9E5EF227DC11","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":"Q1084108$D7D5374A-14E8-4748-BB1E-5763264F363B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8539d1fcf3cff5fbb08dd6973662b887ad57892","datavalue":{"value":{"entity-type":"item","numeric-id":5534028,"id":"Q5534028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084108$EBC3D4F6-264C-430C-AF89-023A48F82541","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":"Q1084108$AA30A509-6151-49CC-8FE4-160D0675E464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e329df2f0401e2bb4067672c9d5324eafb8f0a8a","datavalue":{"value":{"entity-type":"item","numeric-id":4766996,"id":"Q4766996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084108$BEBDF583-128A-4662-94E3-A63735639370","rank":"normal"}],"P1643":[{"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":"3dfefa144bc5f6be44d0875a4f447401dd914d11","datavalue":{"value":{"amount":"+0.8664948344230652","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":"Q1084108$D23D4EE6-8D46-4653-B7AC-49DD60114FE0","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":"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":"Q1084108$725BE491-6268-4979-B33E-08126EB6B7D4","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":"0aea53c69f2a034424bad2b44361b171c08ea40b","datavalue":{"value":{"amount":"+0.8635791540145874","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":"Q1084108$E8D9C399-22A7-4BD6-8658-E5847696FB77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36cd37b616766cb4d447b8273fea0b8b375c66a6","datavalue":{"value":{"entity-type":"item","numeric-id":1895072,"id":"Q1895072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6347244461f35f2c6a2d120fb084c704b25b376","datavalue":{"value":{"amount":"+0.8561990857124329","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":"Q1084108$37028E14-EC89-4FB1-AA51-249D6552D27A","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":"1e3ee3998280579a9a38c00d1f4ad40f46134fb7","datavalue":{"value":{"amount":"+0.8553686738014221","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":"Q1084108$96C08FDF-7312-4E0A-ABFE-6BBC69371A46","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on perfect graphs","badges":[]}}}}}