{"entities":{"Q689957":{"pageid":691806,"ns":120,"title":"Item:Q689957","lastrevid":63508401,"modified":"2026-04-11T13:38:13Z","type":"item","id":"Q689957","labels":{"en":{"language":"en","value":"On a problem concerning tolerance graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 446803"}},"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":"Q689957$EE21660E-613E-4960-8BE6-3A319F2C26E1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"72ccb0a102aacf4b35443583bccfc663dc34f4e5","datavalue":{"value":{"text":"On a problem concerning tolerance graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q689957$C7E6B779-A002-4B74-9AB8-697F0E3BD76C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0e5160e2ac6c2ca4b4cdc6de756110235b290bc6","datavalue":{"value":"0786.05084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689957$50CF6A3C-9190-4CD9-AF33-F1294DB6D7D8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"667bbe68c0ddc29060790745e647bfdde0473bb3","datavalue":{"value":"10.1016/0166-218X(93)90158-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689957$BA8B86CB-D54D-4780-9DF0-FD734BCAC1CF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ea6c9e988b1a5ccaf11509582e9469b2e708609","datavalue":{"value":{"entity-type":"item","numeric-id":689954,"id":"Q689954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$550CDFD3-1BE6-43A0-BD8E-F239D0074C37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e0f13534ef1ebbcce782d09da8eea60b8977092","datavalue":{"value":{"entity-type":"item","numeric-id":689955,"id":"Q689955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$CA99C524-5C55-442A-8F16-0FCAE46F7C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"454f0f66c7edf744c0eeb53f41b6e253cd4bffa2","datavalue":{"value":{"entity-type":"item","numeric-id":689956,"id":"Q689956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$BEB42297-5D02-4A42-BB0B-C60279A7B211","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$C73445B2-55FD-4BAF-B440-F2DBF0E4669F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d0f506d9f4280d6b2b60ede7578329839e1e903d","datavalue":{"value":{"time":"+1994-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q689957$2391E201-E3C2-43C8-AF42-D66EF31877F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c28e8c06427ebc1dda0c90c4c19ccdea81ec83ce","datavalue":{"value":"A tolerance graph is defined as an undirected graph \\(G\\) with the property that to each vertex \\(x\\) of \\(G\\) an interval \\(I_ x\\) on the real line and a positive number \\(t_ x\\) can be assigned in such a way that two vertices \\(x\\), \\(y\\) are adjacent in \\(G\\) if and only if the length of the interval \\(I_ x \\cap I_ y\\) is greater than or equal to \\(\\min(t_ x,t_ y)\\). If moreover \\(t_ x\\) is less than or equal to the length of \\(I_ x\\) for each vertex \\(x\\) of \\(G\\), then \\(G\\) is called a bounded tolerance graph. For a complement of a tree it is proved that it is a tolerance graph if and only if it is a bounded tolerance graph. This is a particular case of a conjecture by M. C. Golumbic, C. L. Monma and W. T. Trotter. Moreover, a complement of a tree being a tolerance graph is characterized by means of a forbidden subgraph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q689957$81E9C0BC-1057-4D8E-9B9F-7E002A10BDF1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689957$0707C48E-38D1-4565-8000-5000C92CED49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689957$DBA0279B-E6C6-460B-9880-4DF335F4FFF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689957$79C12D72-2686-490F-96F2-96C4634C60F0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4c55c5d599c58c324ec0d0d44fc2e62f6f343cac","datavalue":{"value":"446803","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689957$E0345FF2-D5ED-4E77-B47A-A5E4B9E6458E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee4bd296f647a0b2b6777617b5e8acfeee896b9e","datavalue":{"value":"tolerance graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q689957$FE416B33-B319-467B-83D9-5DD5A1BD7286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e95b9d0ea183fb6590dd8803635dc91a1c81ae0","datavalue":{"value":"bounded tolerance graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q689957$0D8C016A-E6E1-4243-BE25-333ABC7A4DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q689957$D21D5D9A-4B1D-4A53-B3FF-7616C0E04E4C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b462d071c33d7d83486f9fef57845bb41d7acf","datavalue":{"value":{"entity-type":"item","numeric-id":190573,"id":"Q190573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$1EDE9102-2179-4975-903C-FF90FFA5B7F0","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":"Q689957$B6ED5A79-4CCD-4665-86A5-82A888E46211","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$F8859A48-7051-4BCA-95BC-006C10DAF282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$D6290EE4-7BE9-4292-9D82-6A5ADF1BC86D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc441cc049bd37d953303b05fb551abe2b633925","datavalue":{"value":{"entity-type":"item","numeric-id":3322150,"id":"Q3322150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$82A4B443-1297-4833-8F3D-24AB6796899A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ddcab77cc06a1867f1053994ad87177b46c2d8a","datavalue":{"value":{"entity-type":"item","numeric-id":798675,"id":"Q798675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$B1001AC0-4F57-4BFE-94AE-1E840200756F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afafd8a1442cf78bf4add4109ea669a8c7f42d8e","datavalue":{"value":{"entity-type":"item","numeric-id":4873748,"id":"Q4873748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$D9049262-5DC0-4696-AA44-D5800D5E7C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39c98f0a6fdd319565369b74be096b9398f842b8","datavalue":{"value":{"entity-type":"item","numeric-id":3984466,"id":"Q3984466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689957$0E677293-5973-4D5B-8502-1E79884386C3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75e97e1ac07c826c325dd6b8a20f925087c70ecd","datavalue":{"value":{"entity-type":"item","numeric-id":798675,"id":"Q798675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3611f17cda5eff8e2187d11e43464d1ce61cabc3","datavalue":{"value":{"amount":"+0.895003616809845","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":"Q689957$3EF3597F-68E3-4E57-A0A8-15607495E5DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eead513a25110173e8ea0482116e90d98cc9de1e","datavalue":{"value":{"entity-type":"item","numeric-id":4242964,"id":"Q4242964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e46522d21a40b86052f13f55f909697b8758d0e8","datavalue":{"value":{"amount":"+0.8841926455497742","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":"Q689957$A5EADA2B-D79A-467F-AACF-18768D5CD622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f215a6f6a06cd19f3bad1f49f3b8f7110d639ce8","datavalue":{"value":{"entity-type":"item","numeric-id":3322150,"id":"Q3322150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e46522d21a40b86052f13f55f909697b8758d0e8","datavalue":{"value":{"amount":"+0.8841926455497742","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":"Q689957$11F0D667-33D6-4D3A-BD5F-47936E5C19B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a209083ccc8fc4eba5f0bdc3d1af5087d46b9dd","datavalue":{"value":{"entity-type":"item","numeric-id":896656,"id":"Q896656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12d43a7fa2526635bf8b3c50686e80ce075abd4a","datavalue":{"value":{"amount":"+0.8617271780967712","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":"Q689957$BBEE9A44-A537-41A1-9922-B0F0FE3D3ECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5cca8dc6a5dcbb703749e5b8c89c95075814be4","datavalue":{"value":{"entity-type":"item","numeric-id":1341250,"id":"Q1341250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85be4979f8cd0e4af54c7afeb756c1f0f4337292","datavalue":{"value":{"amount":"+0.851875901222229","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":"Q689957$64D23715-69BF-4564-B162-4AA16423EA74","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On a problem concerning tolerance graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_a_problem_concerning_tolerance_graphs"}}}}}