{"entities":{"Q1208345":{"pageid":1219094,"ns":120,"title":"Item:Q1208345","lastrevid":69889860,"modified":"2026-04-13T11:01:56Z","type":"item","id":"Q1208345","labels":{"en":{"language":"en","value":"The strong perfect graph conjecture holds for diamonded odd cycle-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 166350"}},"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":"Q1208345$B23E8EF6-1B4C-4FEB-99BC-74CD17503824","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"705598fcd84a56bff360c40fca9495e885f4ff16","datavalue":{"value":{"text":"The strong perfect graph conjecture holds for diamonded odd cycle-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1208345$F8DA6D88-33DF-4980-9357-C4F1BF54C1CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4479ef66465dbd963772dc718b2b1e42c58629c5","datavalue":{"value":"0778.05069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208345$7AEB5AA3-2203-487A-A388-F3FEE941142D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"465b0f038934aac3abd63bc118e8d69a65a2029d","datavalue":{"value":"10.1016/0012-365X(92)90697-E","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208345$0C26AC87-490F-43AF-887C-FA60584B6A6D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fadf5304890e64582a31f3144bc4488d855b9959","datavalue":{"value":{"entity-type":"item","numeric-id":1208344,"id":"Q1208344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$90A00682-F547-41E6-A673-3E6961C594EE","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":"Q1208345$E6A0330D-88E1-4FA1-A173-37EBFC48D086","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1208345$11A117A2-AF94-4427-8942-79F370A84184","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"72bece6d7e762792ba38d325b601eef3c0315c04","datavalue":{"value":"Let \\(G_ 5=P_ 4\\lor K_ 1\\) and \\(J_ 5=C_ 4\\lor K_ 1\\). The authoress defines an odd cycle \\(C\\) of a (simple) graph \\(G\\) to be a diamonded odd cycle if \\(C\\) induces \\(G_ 5\\) or \\(J_ 5\\) or if \\(C\\) has length more than five and two chords \\(xy,xz\\) with \\(yz\\) an edge of \\(C\\) and there is a vertex \\(w\\) not on \\(C\\), adjacent to \\(y\\) and \\(z\\) but not \\(x\\) and there is no edge of \\(C\\) (other than \\(yz)\\) which lies on a triangle induced by the vertices of \\(C\\). She then proves that the strong perfect graph conjecture is true for graphs which do not contain a diamonded odd cycle.   The main technique of proof is to go from the graph \\(G\\) to its clique- vertex incidence matrix \\(M\\) and then to the bipartite graph \\(H\\) for which \\(M\\) is the adjacency matrix between the vertices of the two parts \\(S\\) and \\(T\\) of the vertex set of \\(H\\). The vertices in \\(S\\) and \\(T\\) correspond to the cliques and vertices of \\(G\\). Assuming \\(G\\) to be a minimal imperfect graph without diamonded odd cycles, it is first shown that to verify SPGC (for such graphs) it is enough to show that \\(G\\) has no odd hole of size five or more. Assuming the contrary, it is eventually proved that \\(G\\) contains a star cut set, and a theorem of V. Chv\u00e1tal provides the necessary contradiction.   Several new definitions are introduced to effect the translation of the conditions from \\(G\\) to \\(H\\) and the recent results of Conforti and Rao on balanced and perfect matrices are extensively used. A clear presentation is achieved by breaking up the steps into several lemmas. Even with this, a monstrous lemma (Lemma 6) leads to several cases, only one of which is presented in full detail. For the others, the authoress's Ph. D. thesis is cited.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208345$598E9331-17F1-4B5C-9E74-7A24A0DBB5EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208345$D1D1546F-FD3E-4BB5-ACFE-606605D8850D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208345$49E0070B-B707-4F43-B471-5E4A02C27185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208345$583C03F7-5AF2-40E9-8797-AFF31AD0EBC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208345$DD0EA17F-69A2-400B-A229-D09E5BA55400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"772466e23f65811e4792a58a12ff09d79c338e5f","datavalue":{"value":"05B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208345$9731C708-DE30-4144-BF2E-7169993D7327","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ee2ba4b7b7e27ba7900677e98584f198a957ee46","datavalue":{"value":"166350","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208345$0A6C99C2-AB1A-4F09-AF4D-8CF7DA9A9DCF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a11116a6b4821127d46d686f666f969b50e0a4e","datavalue":{"value":"strong perfect graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208345$E51C7404-3688-4598-AF8D-CB92749F5F35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b1d7594b8da464d6069ed93f9a63322f841ec8b","datavalue":{"value":"diamonded odd cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208345$3932D19F-7D9C-4944-85B6-CF9A076D63C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"262bdfa8edfe99210fd9b6503f70cfab463acd03","datavalue":{"value":"incidence matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208345$52294639-3638-40A5-BB3B-14F25681FFA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208345$8780920B-A92D-4E4C-A074-C1EBF8F93F7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc95e5f05c3d9f83a111dedb75f49c2d26fec40f","datavalue":{"value":"adjacency matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208345$8619D693-4D1F-4644-9025-1FB2C8C4D354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e44d636afeaa789cbf1ac9fd0806b30256871757","datavalue":{"value":"star cut set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208345$D1122523-A99B-43AA-AB8B-B33005FA7FA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db1bd3a3f5e99a0d06c2648b7534792237de74c5","datavalue":{"value":"perfect matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208345$6486D3C8-2B53-45DF-B8F8-D2D3BC92ED20","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1113361299d993aa51c0ae18b9e47bd87a6aa6a8","datavalue":{"value":"Q122924544","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208345$3CA9D688-D325-43DC-8930-B2723FC64879","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":"Q1208345$63805870-915A-468A-B38B-861EE58344B3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"93adb5d47daed89d1d571d53d23af04518295767","datavalue":{"value":{"entity-type":"item","numeric-id":5603089,"id":"Q5603089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$0C69C28C-DB8F-4BD0-A319-6FA414D4CF2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15abf164381e188ffaaaa88e1e51e9c0b99bc916","datavalue":{"value":{"entity-type":"item","numeric-id":5659570,"id":"Q5659570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$1055C2D4-716E-4876-B7CC-8A6FA1036D65","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":"Q1208345$66EF1F38-0BEB-4845-9D3E-AEC515F69667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f3be34444b87e94060eeddaad78e0c69a90fd2","datavalue":{"value":{"entity-type":"item","numeric-id":4165164,"id":"Q4165164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$40553A43-535A-4E67-BC2F-E46BF941D0D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c183b5a6f932d005dd20d44ce907e93d62bf7a89","datavalue":{"value":{"entity-type":"item","numeric-id":1196165,"id":"Q1196165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$A1D6513A-79BF-4E88-93AD-068DDF562B45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"108ba7bf49c0395fea1fae77e724d1c7526e8cf5","datavalue":{"value":{"entity-type":"item","numeric-id":1194854,"id":"Q1194854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$EA44662A-F6E4-4EF4-A75A-F79C77734262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55d0f873a5e787d060846824f11a7c433a75f7f7","datavalue":{"value":{"entity-type":"item","numeric-id":3222219,"id":"Q3222219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$C7B3F91B-F7D0-4753-B038-5B2585223808","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46cea1204e8b56e8cdf89cf3b32e1a95f1f87fb2","datavalue":{"value":{"entity-type":"item","numeric-id":1213881,"id":"Q1213881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$37FBC19D-AEEA-43DD-89E3-DBE0661AA09C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f2ea9e473a8cf61f64728aa7c6cf40b378a168a","datavalue":{"value":{"entity-type":"item","numeric-id":754232,"id":"Q754232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$4FCD5B0A-7C4C-47C2-A8B6-8DE19BF5A25D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cceb1234cc3145b85555d80daa70c1ec324e91e6","datavalue":{"value":{"entity-type":"item","numeric-id":5663885,"id":"Q5663885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$B8C881BB-5E55-4128-B94A-0DF94D1DAB46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7eadd6302524fe0279369bf2a3e30a02dc9c4f2","datavalue":{"value":{"entity-type":"item","numeric-id":2563173,"id":"Q2563173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208345$472DFE09-12BE-4790-8FB2-79F83B1FAB74","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":"Q1208345$2BD5A510-5E24-44FC-A5C2-043DD78F2C23","rank":"normal"}],"P1643":[{"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":"0a6d66a3be248b408a1a2a6383ac5c21f1a33783","datavalue":{"value":{"amount":"+0.8421469926834106","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":"Q1208345$5598A010-8B2D-4D69-97B6-25A7CB723CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a180f0f21ea03b1b174b8847daff62eeb9689b9c","datavalue":{"value":{"entity-type":"item","numeric-id":1921450,"id":"Q1921450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cf83d849a4aa1e498e48756c25397074662ac08","datavalue":{"value":{"amount":"+0.8377920985221863","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":"Q1208345$F96583C4-AF72-4ADB-B39D-A0B3B1325581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0134aab4754c28757b5b04193ed895505a234835","datavalue":{"value":{"entity-type":"item","numeric-id":3688409,"id":"Q3688409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc8092ad8f5f9881ce324023e3d1821d3ce0371a","datavalue":{"value":{"amount":"+0.8363140225410461","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":"Q1208345$D6AFD59C-A35D-477B-93E2-726D610AD96B","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":"9431497f5d02ebf70cf8d57ef33c2ba98489b3c2","datavalue":{"value":{"amount":"+0.8280436396598816","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":"Q1208345$581747C9-BB2C-4F80-BBD2-45AB02B548B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b41cdd6c68a4b0175bbdb432c97bbe800cc41448","datavalue":{"value":{"entity-type":"item","numeric-id":1293187,"id":"Q1293187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb3712be1c17e75ce4fac9fb31c8372502904be7","datavalue":{"value":{"amount":"+0.8264050483703613","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":"Q1208345$18262958-7382-4640-B883-E1AF31F24B10","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The strong perfect graph conjecture holds for diamonded odd cycle-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_strong_perfect_graph_conjecture_holds_for_diamonded_odd_cycle-free_graphs"}}}}}