{"entities":{"Q1567276":{"pageid":1578016,"ns":120,"title":"Item:Q1567276","lastrevid":46898991,"modified":"2025-12-25T19:50:48Z","type":"item","id":"Q1567276","labels":{"en":{"language":"en","value":"On \\(P_4\\)-transversals of perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1455609"}},"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":"Q1567276$37338E79-4D86-4EB7-8973-DC7A8C1440F3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0015043e4df930f788d3b29ebf75e9a2423940e5","datavalue":{"value":{"text":"On \\(P_4\\)-transversals of perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1567276$5C281B60-ABC5-4637-86CD-05F783A94853","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"84f24ebbfb19c0a38e011a5597101fb44f4eb407","datavalue":{"value":"0955.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567276$76D57F52-C640-442E-AB9C-C52579B8CE6E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6f8bd700d60d46af8e943a021ff55da49fbf4bab","datavalue":{"value":"10.1016/S0012-365X(99)00300-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567276$8B73DAB0-269C-4B7F-BEA5-5542D87971F0","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":"Q1567276$767F5893-9399-458C-8118-6097DDFC5C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d58268156f8ce664e47b92662ca397a022d5f810","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567276$C56136EB-4993-47D2-BF7B-A9640A99EF8A","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":"Q1567276$B5856F3E-3B5B-4F61-A55F-B50E82EF2137","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"145372a092458f2e9cd5987368e93e024c6b763f","datavalue":{"value":{"time":"+2001-02-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1567276$8705B54A-72F8-4CC3-B428-97D088D189A1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9db6c2e8d6ae48984ffc6cadc9240f52e254f408","datavalue":{"value":"A \\(P_{4}\\)-transversal of a graph \\(G\\) is a subset \\(T\\) of its vertex set meeting every \\(P_{4}\\) of \\(G\\). If in addition, \\(T\\) induces a \\(P_{4}\\)-free subgraph, it is a two-sided \\(P_{4}\\)-transversal. The authors conjecture that Berge graphs with a two-sided \\(P_{4}\\)-transversal are perfect. A graph is \\(P_{4}\\)-stable if it has a \\(P_{4}\\)-transversal inducing a stable set. It is strongly \\(P_{4}\\)-stable if it has a stable \\(P_{4}\\)-transversal meeting every \\(P_{4}\\) in an end point or every \\(P_{4}\\) in a midpoint.   The authors prove the following: (1) \\(P_{4}\\)-stable graphs without odd holes are perfect. (2) Recognizing \\(P_{4}\\)-stable graphs is NP-complete. (3) Strongly \\(P_{4}\\)-stable graphs are perfectly ordereable (and hence strongly perfect and perfect). (4) Strongly \\(P_{4}\\)-stable graphs can be recognized in polynomial time. (5) A Berge graph \\(G\\) with a \\(P_{4}\\)-transversal \\(T\\) inducing a threshold graph and meeting every \\(P_{4}\\) in an end point or every \\(P_{4}\\) in a midpoint is perfect. They discuss in detail how their results enhance the class of known perfect graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567276$2769959A-563A-432A-AEA7-0243278A2AD7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567276$E88BA919-FDD2-4ACA-99D3-7E4FCC25D725","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71d82e3c4eb2bed58bd3090322c64b89c838ac26","datavalue":{"value":"1455609","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567276$98DF3D0C-8FDD-415E-9D98-BDB1FB9CC9ED","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567276$FFCDD2BE-23F2-4DEC-AE80-3B30596A0D25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbf5385e38f221de9c50063da70e227c011dda95","datavalue":{"value":"\\(P_{4}\\)-transversals","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567276$3E5C4945-63E5-40C8-B796-8E0CAF579357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1299386ebc4f612e1fffd660722437a77f37e1b6","datavalue":{"value":"perfectly orderable graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567276$54345820-8791-4B10-8F80-AF5F2E33D00D","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":"Q1567276$38579881-D1B0-4338-BFC8-AFB175E96A60","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"62684d24501c05644e4f80957d796fa3186526df","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(99)00300-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1567276$E5BF8AC5-3D74-4BE5-9CE7-02605951CCA4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"83522a042eefe7405c2ea23b2f57a50d0cfea4cf","datavalue":{"value":"W2093495451","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567276$1A98CA36-BE90-4F3E-9C12-765142F46EB0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6674c239e0458ab673f7462886cd2bd5babfe3a2","datavalue":{"value":{"entity-type":"item","numeric-id":998435,"id":"Q998435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f2f805492f9e5d8496a866cb916645476f7f85e","datavalue":{"value":{"amount":"+0.8317705392837524","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":"Q1567276$B0900A0F-FD59-4AF5-8A3D-315721222698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e63b2cae24dbb819666fb2799361392bc7e5472","datavalue":{"value":{"entity-type":"item","numeric-id":2758334,"id":"Q2758334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3592e36c33d8a4954eeafcec0a398e0698b1c09","datavalue":{"value":{"amount":"+0.8026467561721802","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":"Q1567276$D1D5BD3D-4AD2-413D-97EB-840E0DDEBD75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f063e869023d81ea48f1e683b98bbd2e2a9b04d5","datavalue":{"value":{"entity-type":"item","numeric-id":3222224,"id":"Q3222224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d25d43c9e88aaf3b0d10d5b5708672b9d166605","datavalue":{"value":{"amount":"+0.8008928298950195","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":"Q1567276$7DFBAE93-A56E-42FC-9C8B-9AC352F889D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0afcdfc75b67d3050edcffb0674f95c8c84ec44","datavalue":{"value":{"entity-type":"item","numeric-id":1104341,"id":"Q1104341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abee794b35efddd7bf2f65b79570644e106fc0e8","datavalue":{"value":{"amount":"+0.7850214242935181","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":"Q1567276$68916DCE-4A0F-4E1D-834F-04169C2AC1B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78b2c02064217895f146ccad55dcce5a355d10b5","datavalue":{"value":{"entity-type":"item","numeric-id":3701463,"id":"Q3701463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6aee277dd568fa2992fea19d7c8ee461b6b2e73","datavalue":{"value":{"amount":"+0.7826088070869446","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":"Q1567276$FA0C9F01-81A1-4645-B86E-07F1249F7083","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1567276","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1567276"}}}}}