{"entities":{"Q1081612":{"pageid":1092364,"ns":120,"title":"Item:Q1081612","lastrevid":48978697,"modified":"2026-01-06T09:33:30Z","type":"item","id":"Q1081612","labels":{"en":{"language":"en","value":"A theorem about a conjecture of H. Meyniel on kernel-perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3970781"}},"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":"Q1081612$CA28DC59-F38B-45ED-B3E0-CFBE0642BBBF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1d7e154b6dc6d9bbd653861ce90c14c2c4a8478f","datavalue":{"value":{"text":"A theorem about a conjecture of H. Meyniel on kernel-perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1081612$E19688E9-166F-4900-B680-E5E65261D7AD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6e939d831fbc24d5870cff389f1ba9cd41fd0d27","datavalue":{"value":"0602.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081612$EE583100-2B01-4270-914B-C4F14F4B0B65","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7ee8d7476f9f049d929f0b08116e6cc871df7e46","datavalue":{"value":"10.1016/0012-365X(86)90066-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081612$4DDB3DA1-24F8-4B14-850E-C4F6D8B69709","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":"Q1081612$F5F1E8B3-3D5B-42C9-95C5-0C3921F81CBB","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":"Q1081612$585F4ECA-CDE2-4DD7-9771-0F0DA54B80F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"864dce0f6f9919c6c0d07e56d8955540e2163f75","datavalue":{"value":"An R-digraph (also called kernel-perfect graph) is a digraph such that all of its induced subdigraphs possess a kernel (that is an independent dominating subset). Meyniel's conjecture (suggested in the title) is that D is an R-digraph if all odd directed cycles of D possess two pseudodiagonals (a pseudo-diagonal is an arc which is not part of the cycle but with end vertices on the cycle). This conjecture was disproved by the author [ibid. 41, 105-107 (1982; Zbl 0484.05035)].    In a previous article [ibid. 48, 67-76 (1984; Zbl 0529.05024)], the author and \\textit{V. Neumann-Lara} proved that any digraph, in which every odd directed cycle has 2 pseudodiagonals with consecutive terminal end vertices, is an R-digraph. The aim of the present article is to show that the same result holds with 2 pseudodiagonals of the form \\((q,q+2)\\) if D does not contain a directed triangle.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081612$77FFA89E-60C2-449E-8723-952AB8753C88","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081612$D3C6E1A2-A41D-4639-AC8D-920AE706A6F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081612$97344663-439A-46C8-9BCC-E33553D3C082","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b8cc29ca3ae6d8ca1a90e887a8cceb63976c00d5","datavalue":{"value":"3970781","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081612$34DE1B25-12DF-42FA-B33F-9F6F54D125DB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6517e1a2e6143e57632ab109df013a46e97349e1","datavalue":{"value":"R-digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081612$9B3C5A60-872F-4003-9346-6F9171E2E919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1fd042b69309e68822a4b088b249f004b73f470","datavalue":{"value":"kernel-perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081612$729FDB1A-EEE4-4B99-9159-1433B6AD1CC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081612$23DA7624-396C-447C-9731-3D07373508B3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"405817f48a9b2e48bac9bc5dd41a81ccfcba3183","datavalue":{"value":"Q123356369","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081612$2EAD1D65-B411-4156-B2EF-6DACFE60494F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"422f975a6f5c5687b63af0336205808cd1c581d3","datavalue":{"value":{"entity-type":"item","numeric-id":251511,"id":"Q251511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081612$CED77EF8-7805-4836-A599-5C478C36CDB6","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":"Q1081612$4EF4C3AB-0A3A-4B68-AABF-F9715373293A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"11ad76d3ddfa7a55b034bc9601241a201bd9cb02","datavalue":{"value":{"entity-type":"item","numeric-id":3912817,"id":"Q3912817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081612$256E532D-CD2C-4E71-BAFB-1083DAA1B56D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9afc90fcd8df3d95188cd6ce543963c50a3be380","datavalue":{"value":{"entity-type":"item","numeric-id":787155,"id":"Q787155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081612$B5DBA952-2110-4843-A83E-208D65279210","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b638422b74f04a7453463c025e00d31d6c1ceb0a","datavalue":{"value":"https://doi.org/10.1016/0012-365x(86)90066-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1081612$580133CD-7D67-4AEB-8E01-5A6B3E82788E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"500803de1cbba7c2c584f5680614c225c5734995","datavalue":{"value":"W2083045902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081612$BE46C504-DBFD-4C5A-BB64-3BAF772B9A05","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b27b297705f4492cd61bd682ad7f27fd25eb4ad9","datavalue":{"value":{"entity-type":"item","numeric-id":3752406,"id":"Q3752406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b587615c6bdeaa3d1c148bca86207f6052e03b17","datavalue":{"value":{"amount":"+0.8630951046943665","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":"Q1081612$DA96CB31-A952-4343-85AD-A1CB1F6F8998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06720d65931890e395f83f3ddc5128cddeb64e2f","datavalue":{"value":{"entity-type":"item","numeric-id":4862105,"id":"Q4862105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1719cf5bb80a26bb3b9ac9c33fc6fa50912a798","datavalue":{"value":{"amount":"+0.834159255027771","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":"Q1081612$4D5780F8-3003-4112-8189-93934EEE1000","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e384b735be2d517fdeafd0bc596f7e63082a3a14","datavalue":{"value":{"entity-type":"item","numeric-id":2785646,"id":"Q2785646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a8ddaf6fa10ded16419e3e9c871427c07a6478f","datavalue":{"value":{"amount":"+0.8328396081924438","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":"Q1081612$0C3AAD02-A25C-4D60-82A9-7C856F748D7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23032988e582dc513b7e868c433540958f3dfe15","datavalue":{"value":{"entity-type":"item","numeric-id":4312247,"id":"Q4312247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c52d050f2ce7616611aef1e15b7846fc89c1b9b","datavalue":{"value":{"amount":"+0.8307496309280396","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":"Q1081612$3E0F7F9B-16D7-44CB-B574-3E3839A2540C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2741df99f9db341a170b4b972307e8a62fcc28c2","datavalue":{"value":{"entity-type":"item","numeric-id":684411,"id":"Q684411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"004609e990015f83b5e6b972dcb397f5bbca3c59","datavalue":{"value":{"amount":"+0.8249551653862","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":"Q1081612$0B5552BF-AE76-4128-B81E-692E90E5FAD6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1081612","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1081612"}}}}}