{"entities":{"Q809100":{"pageid":810948,"ns":120,"title":"Item:Q809100","lastrevid":49528018,"modified":"2026-01-07T12:25:12Z","type":"item","id":"Q809100","labels":{"en":{"language":"en","value":"Orientations of graphs in kernel theory"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4210184"}},"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":"Q809100$99627EA1-D24C-4902-98F5-7EBCEC268E4F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3522d59950489abcefbc9faf680afcb3cfd91be3","datavalue":{"value":{"text":"Orientations of graphs in kernel theory","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q809100$6DA85976-5C29-4DB2-9C1B-15D5AD676717","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f3e381e3f1343427bc9e0e830cca29b9ebe92b4e","datavalue":{"value":"0732.05044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809100$FDA68669-7C29-4872-A3D0-C0DD2379CBAB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"373a2c40385269d45a862aa5343ce0236f204c22","datavalue":{"value":"10.1016/0012-365X(91)90136-P","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809100$C4CBFB7D-E3DA-48A4-81F4-FDD64E20DE1A","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":"Q809100$17748BB6-564B-4206-81EF-B2B8EFDDB496","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q809100$E59CD8CB-2F69-4143-8BD2-CCE32F3EC772","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"991051ac984b81d5856babc41bbb5fe7c061fec2","datavalue":{"value":"The strong perfect-graph conjecture of Berge reads as follows: A graph G is perfect iff G does not contain \\(C_{2n+1}\\) and \\(\\bar C_{2n+1}\\), \\(n\\geq 2\\), as an induced subgraph.    In the present paper a certain class of finite, simple graphs G is investigated which satisfy this conjecture. An orientation \\(\\vec G\\) of G is a digraph obtained from G by orientation of each edge of G in at least one of the two possible directions, \\(\\vec G\\) is called a normal orientation if every complete subgraph of G possesses an absorbing vertex and a kernel of \\(\\vec G(X,U)\\) is a subset \\(K\\subseteq X\\) such that K is independent and absorbing. The treated class of graphs - the so-called \\({\\mathfrak M}\\)-free graphs - consists of such members which have no induced subgraph isomorphic to an element of \\({\\mathfrak M}=(M_ 1,M_ 2,M_ 3)\\) in which \\(M_ i\\), \\(i=1,2,3\\), are special simple planar graphs which are portrayed \\([M_ 1(6,6)-6\\) vertices 6 edges; \\(M_ 2(5,6)\\); \\(M_ 3(5,7)]\\). In the first chapter some structural properties of these graphs and studied which especially result in equivalent statements and from Theorem 1.4 follows that \\({\\mathfrak M}\\)-free graphs satisfy the above mentioned conjecture.    In the second chapter are considered normal orientations of \\({\\mathfrak M}\\)- free graphs and relations to the class of the so-called R-digraphs are proved (in a previous paper was shown that \\(\\vec G\\) is an R-digraph iff every induced subdigraph of \\(\\vec G\\) has a kernel), in which also relations to triangle-free graphs appear. The main result is the proof that \\({\\mathfrak M}\\)-free graphs satisfy the conjecture of Berge-Duchet:    A graph is perfect iff any normal orientation of G is kernel-perfect (Theorem 2.3). To prove it is used Richardson's Theorem: Any digraph which does not contain directed cycles of odd length has a kernel. Finally are considered orientations of \\(K_ 4-e\\) free graphs and the results of this chapter characterize the relevance of such graph classes to the kernel theory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q809100$1244B361-EFFE-4763-B384-E256D0352767","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809100$CBAFAEA8-914B-4557-8DDA-56B3268BC98E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809100$2449CCC7-013F-4133-83D5-7775D9C58DF9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e500d1931c98295ccd2cca6b0166966120fe4657","datavalue":{"value":"4210184","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809100$74076C15-31AD-4C03-8CBF-960026D2E68E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"265017bdf556bec953b209d79a03de570696bb33","datavalue":{"value":"structure of perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q809100$0FFC6A35-D21A-483A-AC5E-8A237441C506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cb9b541d502ee49e1fd87402037bdcf1a31c742","datavalue":{"value":"problems of kernel theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q809100$DA0E0612-9160-4381-9EE4-4552C3751749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb7d657c072426c0a1a64ed7c782b39eecb0338d","datavalue":{"value":"strong perfect- graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q809100$45D0C41A-12D9-49B9-B638-3C4CBFE865B4","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":"Q809100$00F71E35-162A-4C74-93F3-4571B390894E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9cd774068b5ac798da8769c76b801ea4b5bb335","datavalue":{"value":{"entity-type":"item","numeric-id":932667,"id":"Q932667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809100$AE33A7D7-1135-4DC1-9771-12C34925F8B8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809100$5AA14144-6A68-49C3-A0A3-643B13C30F3F","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":"Q809100$0278C143-2956-4109-9792-C02DAA337426","rank":"normal"}],"P223":[{"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":"Q809100$A988862E-5F21-4919-89E1-8F768A06DA7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2d67bd3980ca4eba682fae6d5244771f4d9299e","datavalue":{"value":{"entity-type":"item","numeric-id":3222875,"id":"Q3222875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809100$E02C1BFD-1C29-4C5C-B047-2BCDE672EE75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809100$5AB32546-9372-45E7-B66A-4905354DF665","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":"Q809100$31D74EAD-FB38-498D-8A1B-DD0ADFA60FEB","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":"Q809100$54991AC6-FEF2-4551-ADAD-E88A75E912AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"375ea5a0417924a6827baafef029f9a7e5d9b649","datavalue":{"value":{"entity-type":"item","numeric-id":1172646,"id":"Q1172646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809100$CE0DD6AF-F9C1-430F-9FF7-8EE2D1F33E23","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":"Q809100$F9C03488-74E5-4008-AF20-A84442D8C74A","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":"Q809100$3212C532-195C-444E-885C-8EDF7994DEDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27efb0821c1b2200379029b93d25a684ffc90920","datavalue":{"value":{"entity-type":"item","numeric-id":1182966,"id":"Q1182966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809100$15196A98-C128-4E3F-884D-8591B79D6126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32717a41c30ac9f2c74badd1163dfcf82366e76e","datavalue":{"value":{"entity-type":"item","numeric-id":1163568,"id":"Q1163568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809100$9FA9A6F0-B47C-49B3-B6FA-445F3E2D1648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f52d9d188afafd533c9d0a2ec2edab68e37d2913","datavalue":{"value":{"entity-type":"item","numeric-id":1081612,"id":"Q1081612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809100$C555C103-6CA9-4EC4-8F0E-0D752992C8DD","rank":"normal"},{"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":"Q809100$C1013E3C-A880-4BFD-9AD1-09AE853B5E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc9a2a8f0af76a8e59e5dcd24326111a1d57d402","datavalue":{"value":{"entity-type":"item","numeric-id":2651359,"id":"Q2651359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809100$B0184F19-1CBF-4C89-ACA2-24297CB2386D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4eb43d7fb65f2efc2f242a66aafcb042bdca51c3","datavalue":{"value":{"entity-type":"item","numeric-id":5823356,"id":"Q5823356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809100$79F6C697-E38B-4CB1-9D66-DE10DDFAEF63","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9815d3308ffde546ef4d34cc676a7d9c476ae0b8","datavalue":{"value":"https://doi.org/10.1016/0012-365x(91)90136-p","type":"string"},"datatype":"url"},"type":"statement","id":"Q809100$38590CC4-ABC8-429E-BC75-5263A7B07329","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8c9108d9c572e3b8c7ff26ea70f1d0c378f0954b","datavalue":{"value":"W2074536685","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809100$B568AFDF-A3E6-490E-B05D-1431557F8FB0","rank":"normal"}],"P1643":[{"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":"f42957575aed84f1cad4786e01352fdcef82fd9f","datavalue":{"value":{"amount":"+0.85968017578125","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":"Q809100$867ED5D8-5084-4775-86B5-BB642BF7E0AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"686098137f3898db50d064680787983fe73eb969","datavalue":{"value":{"entity-type":"item","numeric-id":1357743,"id":"Q1357743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eea2d003afbb585d051f0709ab7c48dbb91b795c","datavalue":{"value":{"amount":"+0.8464417457580566","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":"Q809100$EED39F46-5F8E-4EBB-858B-721083EEAA17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f116098a0940ff230fa7cdda2c62df06a8be4ac","datavalue":{"value":{"entity-type":"item","numeric-id":1313857,"id":"Q1313857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eea2d003afbb585d051f0709ab7c48dbb91b795c","datavalue":{"value":{"amount":"+0.8464417457580566","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":"Q809100$FC0C63AE-CE66-4F3B-923D-121B20DC8350","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":"3e17f6c4fedb0b133477cc2e9b31643ed7255953","datavalue":{"value":{"amount":"+0.839493453502655","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":"Q809100$640B7F70-0D94-4509-A978-48F751DDC244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97bffdf8cddca61053fc826fb9eafb62d9d46c06","datavalue":{"value":{"entity-type":"item","numeric-id":3822190,"id":"Q3822190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a3577601363ebd68dd74c71ed6e46bfad635add","datavalue":{"value":{"amount":"+0.8319963216781616","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":"Q809100$1142EC7C-FED2-4BFD-A1BA-19A6051EB9F6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:809100","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:809100"}}}}}