{"entities":{"Q1121917":{"pageid":1132666,"ns":120,"title":"Item:Q1121917","lastrevid":66814830,"modified":"2026-04-12T13:02:47Z","type":"item","id":"Q1121917","labels":{"en":{"language":"en","value":"String graphs. I: The number of critical nonstring graphs is infinite"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4105013"}},"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":"Q1121917$B705B778-A41A-4AA5-A535-A18C4C8B7971","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"910017e3c886e76ad301402b3a784ed7e486527c","datavalue":{"value":{"text":"String graphs. I: The number of critical nonstring graphs is infinite","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1121917$F568725F-8D2F-4F1C-AC02-EAF3F1D0C117","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"925811ed896c7297fddc0383327d1b9aeccb2136","datavalue":{"value":"0675.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121917$28FFC737-3392-4DF4-ADE0-790929E8E25F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f61911df53db120eee385d6c58e9631ab85a1177","datavalue":{"value":"10.1016/0095-8956(91)90090-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121917$E5F0C3CB-3E68-495A-B478-024464AD9D31","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9034d743abb2e8189da1fd67afac14b0cf3088f3","datavalue":{"value":{"entity-type":"item","numeric-id":175587,"id":"Q175587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$95BAD19A-F640-4E28-A911-1811F83D4976","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":"Q1121917$44358C3D-80B7-45D6-ACD6-3F45470D77AF","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":"Q1121917$E8FCAF47-EB9F-47AE-8ABF-881BB57DC973","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9d1afb0489cf86a177cd29fa342fd1468e1b041c","datavalue":{"value":"String graphs (intersection graphs of curves in the plane) were originally studied in a connection with RC-circuits. The family of string graphs is closed in the induced minor order, and so it is reasonable to study critical nonstring graphs (nonstring graphs all proper induced minors of which are string graphs). The question whether there are infinitely many nonisomorphic critical nonstring graphs has been an open problem for some time. The main result of the paper settles this question. In a later paper of this series we show that recognizing string graphs is NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121917$F085D5FC-24A8-4F5F-93F9-4FF925608E08","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121917$BBC77392-E80C-4DFF-AA62-1A5FE2B95CCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121917$2BB798BA-2865-42FC-8E53-547B3CB01B3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121917$C06139F2-68FD-44CB-82FF-F07D04D3DC10","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4b4842ec454152b5b3ebd4f253bfe6201407a93a","datavalue":{"value":"4105013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121917$BC660470-F4FD-424D-A9D0-D63A17084237","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aaf8999f734989f237c56b345d8f8a0b83c93a88","datavalue":{"value":"String graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121917$1AA49262-2A0C-42D6-9CD8-19E53E59B9EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25f8eba8c9d529f212c848e074f37e4d66acf3cf","datavalue":{"value":"intersection graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121917$33D9F057-AD30-4F48-A828-78350F00070C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96b85234a4088d208056ca17e9813378a6ff0b75","datavalue":{"value":"curves","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121917$65F77917-6E53-40E8-B6E3-299C87D742E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cda5c404e316fc25d7486edab17961a279d65b7d","datavalue":{"value":"induced minor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121917$E5899675-A059-4790-8661-A5C9BF189583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"148aa77c0cad706c3f9e8395c86c0f4da5cfd584","datavalue":{"value":"critical nonstring graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121917$304ACF6A-D7FB-4A16-B321-88B1236B6011","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":"Q1121917$9D4D8D82-5AFB-4F2C-A9A3-74E0C7A56DCC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8e42726460f14f85f48043ffc299059ff4600831","datavalue":{"value":"https://doi.org/10.1016/0095-8956(91)90090-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1121917$A08B9977-35B7-4CB9-8363-514139F1B839","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1ab83a0acc43a50ee882735bde2c0f84815cf4e6","datavalue":{"value":"W1983826065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121917$276C5E1B-4221-4361-A058-B4B2EF345200","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e584cb82f13d31f8a03a6c13bdb408e1c093f86","datavalue":{"value":{"entity-type":"item","numeric-id":1234300,"id":"Q1234300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$B1249036-1C0F-4D89-9650-1D72E4BAC747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83ab81b85457f990d5674daf61fc32a97eb26853","datavalue":{"value":{"entity-type":"item","numeric-id":1254334,"id":"Q1254334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$DA03B772-08DE-477C-852F-1E37212D1552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e458531dc8f9b4a4f76ca8cb6a5d9d31ac768ee2","datavalue":{"value":{"entity-type":"item","numeric-id":2562090,"id":"Q2562090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$E448190E-7AEA-4CFB-8E32-E71CFEA07E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$038DDE83-5DC0-402C-B2D2-89A578ED8F1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8cfed7f4900e3e265b78f148b39a5857eb957a6","datavalue":{"value":{"entity-type":"item","numeric-id":1172652,"id":"Q1172652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$66486F00-B19E-43F3-B7EC-6356A580B577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff7677c8823f961be1caec5b996508c8f1452da5","datavalue":{"value":{"entity-type":"item","numeric-id":1572015,"id":"Q1572015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$C8A12E20-44D7-46B9-978E-184F830C8B25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c782da8cc8edba3e988eaf1db2b9c2a33d97f8c","datavalue":{"value":{"entity-type":"item","numeric-id":3309881,"id":"Q3309881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$AA43541B-66B6-402C-88DE-6BA94691D715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6890f0de4684848214a64aefe68fe2ed89d12b9e","datavalue":{"value":{"entity-type":"item","numeric-id":3745859,"id":"Q3745859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$0C5E9558-8806-4720-827A-6015FE8F0A80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac9a0e7ebed83e72d9b8966739b88f8b43a3f5d8","datavalue":{"value":{"entity-type":"item","numeric-id":1112845,"id":"Q1112845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$E1884856-BBCB-422E-98CF-4E3BAC1D72D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e666d43d8a517121692b5641daf0b3ee081d310","datavalue":{"value":{"entity-type":"item","numeric-id":3821580,"id":"Q3821580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$D823BF42-D6E3-49C3-B409-497D404ACB49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cd900a9928338cdadd8e18c47b33b430f9560c7","datavalue":{"value":{"entity-type":"item","numeric-id":5602691,"id":"Q5602691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$9C092A8B-958B-4840-B25D-CAFE4A3E1D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"398ef8bc27e00efd8312d46a33efaa0333728c17","datavalue":{"value":{"entity-type":"item","numeric-id":1892832,"id":"Q1892832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$FE650C5D-4D93-4354-999D-871063D3E9D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56ab210fff5d79b2e4d4ad18f1a46804c4d49944","datavalue":{"value":{"entity-type":"item","numeric-id":1410732,"id":"Q1410732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$74B8657A-9975-4B9E-964E-734849FCCF77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2988b845f9f26b26a2975f2631350fdbb3d7c2","datavalue":{"value":{"entity-type":"item","numeric-id":5521330,"id":"Q5521330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$18C0C61A-4337-4300-8510-001F2C22BEFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f8aa6e8119e47ffd0580ffcb40fdaf914002045","datavalue":{"value":{"entity-type":"item","numeric-id":686503,"id":"Q686503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121917$21255290-AA2B-449A-8F73-815C51221B13","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"babde557e5cdbec10149a2d9acaaa7b4467a3789","datavalue":{"value":{"entity-type":"item","numeric-id":1112845,"id":"Q1112845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d96dfe7f2637bc0e2cb8674e99a0c0f31491b0ed","datavalue":{"value":{"amount":"+0.9274638891220092","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":"Q1121917$E77E5070-20AB-4B53-9FF8-F058012A81B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22d9f399ae292852db0c9f17eefc09edbc25235e","datavalue":{"value":{"entity-type":"item","numeric-id":5917583,"id":"Q5917583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23f8b8b54224fb6213028a306062fafc9a5defad","datavalue":{"value":{"amount":"+0.901042342185974","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":"Q1121917$7C6E968C-77C9-4843-B02E-37367DB36B89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb64455cd090b03368f8e065fba02df7463238c6","datavalue":{"value":{"entity-type":"item","numeric-id":3745859,"id":"Q3745859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c0f6b1e27884a1ef4591fd9db57a85f6cde0a05","datavalue":{"value":{"amount":"+0.8994966149330139","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":"Q1121917$CC3BB117-2AA6-412A-9309-226B9D3E12B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b20e1807c536a86a6c744fdcf27ef729fe6eb681","datavalue":{"value":{"entity-type":"item","numeric-id":3474685,"id":"Q3474685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a48ef580d15e74572c4f5c5e5a215d3df072c933","datavalue":{"value":{"amount":"+0.8884870409965515","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":"Q1121917$B34C7699-801E-4567-8407-26877B545641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df196f8c4e2e7cba7ebb5c0ac09d7ba40dd496d3","datavalue":{"value":{"entity-type":"item","numeric-id":1201270,"id":"Q1201270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c7da7c31104efaf8d75e8afb7325348fbbe312b","datavalue":{"value":{"amount":"+0.8503760695457458","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":"Q1121917$5B0DF1A0-405C-4F91-8DE4-FC2999027D65","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"String graphs. I: The number of critical nonstring graphs is infinite","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/String_graphs._I:_The_number_of_critical_nonstring_graphs_is_infinite"}}}}}