{"entities":{"Q685562":{"pageid":687411,"ns":120,"title":"Item:Q685562","lastrevid":78195983,"modified":"2026-05-06T11:01:01Z","type":"item","id":"Q685562","labels":{"en":{"language":"en","value":"On a class of kernel-perfect and kernel-perfect-critical graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417444"}},"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":"Q685562$603246B0-6DCC-4493-B1BD-4631DFE107BA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7914aa7804d1ab8da7f0867505290b0192571b49","datavalue":{"value":{"text":"On a class of kernel-perfect and kernel-perfect-critical graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685562$BE5EE390-B84A-4B00-B85E-F3912A1139B4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68650b92f6b2883dfdffa32fa6c0799f487d67d2","datavalue":{"value":"0782.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685562$8355CB74-850F-4390-A032-231DF12D07F0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"14e0965d7d7e8d04fd816ad24126f85ce9669160","datavalue":{"value":"10.1016/0012-365X(93)90068-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685562$BC87A5A5-843E-4591-BE19-740A026324AA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1b49fddf25bf33367a70c6e3e427af794682e9c","datavalue":{"value":{"entity-type":"item","numeric-id":685561,"id":"Q685561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685562$2AE6C88D-6068-4DDA-95C6-B42F1FB6AA07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"06f41783cb6eb3a86211d59cba9ff7b62f6ba634","datavalue":{"value":{"entity-type":"item","numeric-id":293602,"id":"Q293602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685562$2ABC0A1D-ADAF-4B29-A43D-A1E363144226","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":"Q685562$108808DE-2774-4C0A-8A42-E535C7F74BBB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"424ab2d1dcf625883da0ac65efa262e77659f17c","datavalue":{"value":{"time":"+1994-02-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685562$9D08C6C0-C4F0-4963-AB49-4A2DA946A76F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"663e4d717f80bca3addbe7de4379270f754c2607","datavalue":{"value":"Let \\(G=(V,E)\\) be a directed graph. Then a set \\(K\\) of its vertices is called a kernel if \\(K\\) is an independent set, and \\(K\\cap \\Gamma^{- 1}(K)=\\varnothing\\), \\(K\\cup\\Gamma^{-1}(K)=V\\), where \\(\\Gamma^{-1}(K)\\) is the set of all the vertices \\(x\\) of \\(G\\) such that there exists \\(y\\in K\\) with \\((x,y)\\) being an arc of \\(G\\). \\(G\\) is called a kernel-perfect graph if all induced subgraphs of \\(G\\), including \\(G\\), have a kernel, and it is called a kernel-perfect-critical graph if \\(G\\) does not have a kernel but every proper induced subgraph has. In the paper a new construction of both kernel-perfect graphs and kernel-perfect-critical graphs is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685562$D5F4714A-9B21-448D-BCA9-476FBF681669","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685562$283FB861-C413-4ED9-AC5B-D7795E596904","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685562$18AEB551-C410-405A-BBEE-C2256D2DB7D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3e621a4ac51926ced240b42536f047d4367b1ca6","datavalue":{"value":"417444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685562$04C87A5F-8B97-40E9-94B1-CDE5354A60ED","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf023653318cc5b8c727563611596d2cf1a818a","datavalue":{"value":"directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q685562$8FB05A5B-3EFC-41C2-8D63-91A7F456CCBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6502121864a1dff048ddc4823cf928079ab042bc","datavalue":{"value":"kernel","type":"string"},"datatype":"string"},"type":"statement","id":"Q685562$D65DFEAE-1312-4CF4-81C0-0E41CAE8DC07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1fd042b69309e68822a4b088b249f004b73f470","datavalue":{"value":"kernel-perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q685562$0B9F7F9C-F65A-4323-8E75-F4A5C9616143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc4ee5c94c1927569543c2027f4b7252ddee4a40","datavalue":{"value":"kernel-perfect-critical graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q685562$C81E26B8-1ECF-4A7E-AFE5-FF377454A14E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ef22b67971c907f35c542e2435922e6c49358d32","datavalue":{"value":{"entity-type":"item","numeric-id":215558,"id":"Q215558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685562$0CFAC938-A5F4-475B-ACFE-93B09F3BF05F","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":"Q685562$4F2735C5-3645-40A7-BD66-CC5B9FE85A68","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c666a79fc592174c4038c17bb6d8f45ed067fdd","datavalue":{"value":{"entity-type":"item","numeric-id":5844986,"id":"Q5844986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685562$7611BD59-7749-493A-8E26-0A3050909E72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685562$D51B3ADA-FA32-4920-A399-589D46DCEC95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b4b86e0f0f4bd5ab60b03d2efa59f5471dc96b9","datavalue":{"value":{"entity-type":"item","numeric-id":1076036,"id":"Q1076036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685562$49349140-6D04-4934-A6E7-F0BA054B4D9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9ade079220df28b2680c55c3a07ba26f944e283","datavalue":{"value":{"entity-type":"item","numeric-id":1150376,"id":"Q1150376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685562$13D6877C-83F4-47A5-B8CA-2CE343606262","rank":"normal"},{"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":"Q685562$E8167320-6B06-4DEB-AE19-790E1EC9D981","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"968a06f5e23f50d2ae5d898fb0fb1e87a786e9b5","datavalue":{"value":"https://doi.org/10.1016/0012-365x(93)90068-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q685562$FF88BC09-9C60-46B6-A8D9-9FC2D0792BEB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1d0d4135d23a5fbc82772902de1ae0ae5eb812e5","datavalue":{"value":"W2035216900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685562$F6592E6C-2302-4716-81DF-D2B870614C66","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4746445562cb4725b42b611fa988c55dc13e6c9c","datavalue":{"value":{"entity-type":"item","numeric-id":1076036,"id":"Q1076036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e04a86543616c6fa285dd3fd063d7cd08a41efc","datavalue":{"value":{"amount":"+0.8965893983840942","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":"Q685562$496770A7-A146-4841-AEFE-A3168C1F6E62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43b8c8f344cefdf9873ef6f4e7a72ce301eafb9c","datavalue":{"value":{"entity-type":"item","numeric-id":1343226,"id":"Q1343226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d1ac82b3bbd5c33a352d489bc89518948e79e77","datavalue":{"value":{"amount":"+0.8831204175949097","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":"Q685562$7B15ECE7-EC11-40E5-8ADD-7DBE7018C795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a41df1876999fc944bfed650cd1f1078c94829cb","datavalue":{"value":{"entity-type":"item","numeric-id":2640613,"id":"Q2640613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a9be1665bc9f16aac877ec473c864ff29083ac7","datavalue":{"value":{"amount":"+0.8821930289268494","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":"Q685562$FD6B4330-66B2-4924-AD1F-677EED7991E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1dd3e016348176b20ce656b5654c709d4acce3b2","datavalue":{"value":{"entity-type":"item","numeric-id":1121904,"id":"Q1121904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb40a555cfb42cafce696486f7bc03d54a2f6551","datavalue":{"value":{"amount":"+0.8782496452331543","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":"Q685562$AF56D0C8-9FC0-43C6-B4F5-2AB8CE0321CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b1d3d8c114316a715961e06691a5423a13b1c43","datavalue":{"value":{"entity-type":"item","numeric-id":3439612,"id":"Q3439612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1b0cd90970589295a4280c12904873a30ee856e","datavalue":{"value":{"amount":"+0.8737490177154541","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":"Q685562$DE3DFB30-06EE-43BA-9E1E-0D000427E964","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On a class of kernel-perfect and kernel-perfect-critical graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_a_class_of_kernel-perfect_and_kernel-perfect-critical_graphs"}}}}}