{"entities":{"Q4508370":{"pageid":6537963,"ns":120,"title":"Item:Q4508370","lastrevid":108643535,"modified":"2026-11-09T14:35:40Z","type":"item","id":"Q4508370","labels":{"en":{"language":"en","value":"On dart-free perfectly contractile graphs (extended abstract)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1512683"}},"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":"Q4508370$834D835C-109D-4538-B69B-688F4458432A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f4703b31353b0906d80f3609649a60eee54c8c58","datavalue":{"value":"0969.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4508370$EF9F1527-CDC5-47D3-AF7C-3C78AD0ED5AB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"74e45c3f99221d7833194d9c586d4b22f068b569","datavalue":{"value":{"entity-type":"item","numeric-id":189439,"id":"Q189439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4508370$5A978A94-4A9C-4B04-8E62-8016A8C79A07","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":"Q4508370$DB9401D6-64D8-4461-90DC-F06CA54C4479","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"73fe45a81271f1e06047daf6368e7c43c5b4b14d","datavalue":{"value":{"time":"+2001-02-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4508370$210736BF-E52C-4EE9-A092-7C61F0ACCD62","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4508370$2B7BF23E-CCA8-49E9-BC53-3C2D05D8F1FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4508370$92BE0533-642D-49C9-8687-B21EF63D4873","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b038ed6b7a735c9fdde19f55fe1f08893c2c75cf","datavalue":{"value":"1512683","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4508370$B9F43A8E-85C5-43D1-BBD6-793AD44E7143","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4508370$6B404EED-6625-4004-A86D-30FD0C493A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf2bdc388a8c2bee548ba5c2acc5f66c693118c4","datavalue":{"value":"claw-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4508370$9846F230-1CC3-4D0C-8B2B-79930A04E46B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcedb5f92bea770f2d9a4a6db846da57afcfdf8b","datavalue":{"value":"even pair","type":"string"},"datatype":"string"},"type":"statement","id":"Q4508370$3632652F-13CC-461A-8452-922EAFBFB787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0ac5accbd6ab88629e4490340cc3c1ac3c0df2b","datavalue":{"value":"contractions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4508370$6DF5A8B6-4242-46A8-A4D9-67A3CF8D10A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"583ae4a782a4b0f5bc359c7b8eed7e3d923f41c3","datavalue":{"value":"degree sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q4508370$547E9D50-67B4-46EF-9C1C-8AA85E1BBDCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6cb711d1ba0e55b33da9d0624dc6db2f7aa5d02","datavalue":{"value":"dart-free perfectly contractile graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4508370$21791A48-860B-4104-AE60-DB6516CF89B0","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":"Q4508370$BAEEAF85-22BD-4C52-8169-C4ED0A1307F2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95b834687ea4f2b435c6a736c779d62d0be2b1b4","datavalue":{"value":{"entity-type":"item","numeric-id":1885896,"id":"Q1885896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b27b09137ffdb18233caa7abd11093576efe81e","datavalue":{"value":{"amount":"+0.968716561794281","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":"Q4508370$3DCECE2C-567D-47A5-9402-2FA007055F9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e15012bbd4375192d34ac02ebe8100e9842bda94","datavalue":{"value":{"entity-type":"item","numeric-id":1356748,"id":"Q1356748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6807698627c454457dc701942159b3816c07edd","datavalue":{"value":{"amount":"+0.8593222498893738","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":"Q4508370$7920E6E4-799B-4818-AFC8-4D85EA5A592B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e493701ebac334b50a5e794e52531c3f0004e3f3","datavalue":{"value":{"entity-type":"item","numeric-id":1359374,"id":"Q1359374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6807698627c454457dc701942159b3816c07edd","datavalue":{"value":{"amount":"+0.8593222498893738","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":"Q4508370$DE9F430E-BACB-4AEA-8853-9450989F0B96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f30b05b1de98c1d15fbbcda47a6d4112bb4018c","datavalue":{"value":{"entity-type":"item","numeric-id":2758333,"id":"Q2758333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30361888135df50127ce1023614874f13705035f","datavalue":{"value":{"amount":"+0.8496248126029968","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":"Q4508370$10B32488-D2BD-4971-AD8A-31EED8F8F5D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c47133308fcf6c6cd7eb6ebbca16a4daa843856d","datavalue":{"value":{"entity-type":"item","numeric-id":2581496,"id":"Q2581496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30361888135df50127ce1023614874f13705035f","datavalue":{"value":{"amount":"+0.8496248126029968","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":"Q4508370$24D64275-41E6-4721-839E-DD1330B5DA5B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dee5bee01bf2e7127b6b5335bede865561f14a75","datavalue":{"value":{"text":"On dart-free perfectly contractile graphs (extended abstract)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4508370$223AF914-82BF-41AB-8ED1-20EF0E737F25","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4affc94e6517d5b9a23c6e1a4f9b4117de40cbc7","datavalue":{"value":"10.1007/10719839_15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4508370$77182291-4ECE-4737-8C11-09103D34EC11","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b903a362d5b6f6a50508f8004eb7b7311fb725a5","datavalue":{"value":"An even pair in a graph \\(G\\) is a pair of non-adjacent vertices \\(x\\), \\(y\\) such that every chordless path of \\(G\\) between \\(x\\) and \\(y\\) has an even number of vertices. A graph \\(G\\) is even contractile if it is possible to contract \\(G\\) to a clique through a sequence of contractions such that each contraction is applied to an even pair in the current graph. If \\(G\\) has the property that every induced subgraph of \\(G\\) is even contractile, then \\(G\\) is called perfectly contractile. The dart is the 5 vertex graph whose degree sequence is 4, 3, 2, 2, 1. The main result of the paper is that a recent conjecture by Everett and Reed on the forbidden structures for perfectly contractile graphs is true for graphs that are dart-free (that is, contain no induced dart). The proof implies a polynomial algorithm for recognizing dart-free perfectly contractile graphs. For the entire collection see [Zbl 0935.00049].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4508370$7C419348-C2C4-4DE8-B94A-A9DFDDD0A764","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4508370$7FDE3BE3-A6AF-40B9-9D4A-31FD1CFA1609","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On dart-free perfectly contractile graphs (extended abstract)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_dart-free_perfectly_contractile_graphs_(extended_abstract)"}}}}}