{"entities":{"Q1924145":{"pageid":1934887,"ns":120,"title":"Item:Q1924145","lastrevid":73923357,"modified":"2026-04-14T17:44:41Z","type":"item","id":"Q1924145","labels":{"en":{"language":"en","value":"On the \\(P_ 4\\)-structure of perfect graphs. V: Overlap graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 934812"}},"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":"Q1924145$7438A826-7737-4B62-9C1B-0B58E7FBE9E5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a596f2f1cd44985409f13f5e4fc7e2a959ab5a29","datavalue":{"value":{"text":"On the \\(P_ 4\\)-structure of perfect graphs. V: Overlap graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1924145$B9A6CCA6-CAA9-416E-A74E-73DA644F0D7F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ecdec61b1acabc3bd61f294578d67e59ce5db65d","datavalue":{"value":"0871.05019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924145$1FD5AED9-C0B8-4107-A929-BB981B719397","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7598b946dc98bf1d17807d2ef3a244f2419361f8","datavalue":{"value":{"entity-type":"item","numeric-id":234396,"id":"Q234396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924145$871E71B7-DA18-42D1-976C-86001A273C24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"62ff535d2ba7354e7303f2e291d7bfd613cdf256","datavalue":{"value":{"entity-type":"item","numeric-id":495036,"id":"Q495036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924145$2EF928D4-8015-42D4-81D7-70BF4B2F4147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec2d7eb4aa6a054061ffef53b12788916e0dba01","datavalue":{"value":{"entity-type":"item","numeric-id":222618,"id":"Q222618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924145$D0F6961B-904D-4BD0-B1B1-C8D112B53D38","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924145$AD79DE6B-12FE-4466-A676-075827602F5A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ebd3388ceea5c5819c326b4408c80720ae63a3f0","datavalue":{"value":{"time":"+1997-09-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":"Q1924145$235B2746-47DC-4A78-BDFD-44374A3F1E34","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5c742125e576b5cc33a8f96a1222a6bf87c4690b","datavalue":{"value":"An odd hole in a graph is an induced cycle with length odd and at least 5. A Berge graph is a graph with no odd hole or its complement. The \\(k\\)-overlap graph of a graph \\(G\\) has a vertex for each induced \\(P_4\\) in \\(G\\), and two vertices are adjacent if the corresponding \\(P_4\\)'s have exactly \\(k\\) vertices of \\(G\\) in common. Here \\(P_4\\) denotes the path with 4 vertices.    It is shown that for \\(k=2,3\\), if the \\(k\\)-overlap graph of a Berge graph is triangle-free then \\(G\\) is perfect. This yields that if the 3-overlap graph of \\(G\\) is bipartite then \\(G\\) is perfect, and if \\(G\\) is \\(C_5\\)-free and the 2-overlap graph of \\(G\\) is bipartite then \\(G\\) is perfect. Similarly, if \\(G\\) is \\(C_5\\)-free and the 1-overlap graph is bipartite then \\(G\\) is perfect. The result for \\(k=3\\) extends some recent work on `partner graphs'.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924145$BF74BC33-77BA-4DE9-B2E0-F24CEA9529C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924145$A8633835-543D-4CBF-989E-E8B81C71DDA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924145$BC799F6D-E386-4086-AFDA-403615DD64CA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1dda8a5c1affd95c99c2bd117e51ecdb3fe74299","datavalue":{"value":"934812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924145$78E77365-FE29-4F5F-96CE-13B5A906DC8F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924145$43AF7807-383B-44E0-913C-3C2742E3848F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ee031bee4a482dd39d28c0a47e98e5aac5c6d01","datavalue":{"value":"overlap graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924145$E6356234-5FF8-437D-8372-C462DD018A20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0781dea49020fd5028774cbbf789a94ac1263f85","datavalue":{"value":"odd hole","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924145$A2D0D94D-8A79-46FF-A819-68960302F57B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924145$E349C5E1-7C6A-420B-B9E2-2B4B300A072A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5594bf089e20db614ce61dae32b887cd362d61e2","datavalue":{"value":"Berge graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924145$8D4E7E41-B92A-4155-9339-39F2A7CF6186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4aaaa8a20aebc13233df640115f8b0d384236cf5","datavalue":{"value":"path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924145$68A12C5B-2404-4CD5-A6BB-C1C482E10F3E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f6b4f90049fe624e4c23d9606bae564b5e305267","datavalue":{"value":{"entity-type":"item","numeric-id":1227010,"id":"Q1227010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924145$0903F93E-01EE-4FF9-BD57-9797FA8D066F","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":"Q1924145$2320CB27-F6EA-47C0-9FBB-07C6123EA1E7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6cc9d039292dc264b6a4c3c735476e1e3423f5e8","datavalue":{"value":"https://doi.org/10.1006/jctb.1996.0042","type":"string"},"datatype":"url"},"type":"statement","id":"Q1924145$043F3119-7300-4859-AA68-A20E83B1A8D0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"791f53be317cfd1e971338e424e2cceb7c61123d","datavalue":{"value":"W2057237215","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924145$D0D595D7-3957-4DDF-BBE3-AF09C4312C2D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b4d69130a61586d239bdcd632f3e131fc6599f71","datavalue":{"value":"10.1006/JCTB.1996.0042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924145$65325821-CDCC-407D-9D57-2DBF355A9369","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4add5281769213f2043556c93c255714beedfd3","datavalue":{"value":{"entity-type":"item","numeric-id":1112847,"id":"Q1112847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cd341771dd12c7daaecbec5bf13fbad265ab53d","datavalue":{"value":{"amount":"+0.7907575964927673","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":"Q1924145$737CDB19-32A9-4118-88F1-296352FCC9C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86ebf04eadc1764a0307875fd7dd0df28a065844","datavalue":{"value":{"entity-type":"item","numeric-id":1332433,"id":"Q1332433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f8e221694ed4044fa6a52573c657924474434b6","datavalue":{"value":{"amount":"+0.7877927422523499","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":"Q1924145$48D6040D-590A-43E3-BA66-26CF7A3DDB7A","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":"433707d7ff46cf4f35f597095fb4771484f3b67c","datavalue":{"value":{"amount":"+0.7845160365104675","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":"Q1924145$47DDC2A0-40E1-4E21-BCD7-22FFD60A3C94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc6e9e9c0eac84699f6231eef9bdf7520323946e","datavalue":{"value":{"entity-type":"item","numeric-id":1812828,"id":"Q1812828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59370c6461fd7ad2e7102a4453291c025e5402d8","datavalue":{"value":{"amount":"+0.7835188508033752","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":"Q1924145$C2A08481-62C5-4362-8E25-4BF28DAC8CE6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the \\(P 4\\)-structure of perfect graphs. V: Overlap graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_%5C(P_4%5C)-structure_of_perfect_graphs._V:_Overlap_graphs"}}}}}