{"entities":{"Q2758062":{"pageid":2768801,"ns":120,"title":"Item:Q2758062","lastrevid":83135087,"modified":"2026-05-07T06:15:51Z","type":"item","id":"Q2758062","labels":{"en":{"language":"en","value":"Forbidden subgraphs and forbidden substructures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1679335"}},"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":"Q2758062$B4C589CE-A953-4518-9300-7E1E8A918AC6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9bb645a9f542c3b5406358181b1ed69ea2275cf0","datavalue":{"value":{"text":"Forbidden subgraphs and forbidden substructures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2758062$76384177-7E59-4AA6-833F-0641D9038DEF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"567e745510930b250c7ca8d456bd494c0e87e464","datavalue":{"value":"0986.03029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758062$2FA3C8BD-74A4-4116-9171-4B2E0F8B6BF5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fb1b0992287639835ca2f65ef4cc7f8241468068","datavalue":{"value":"10.2307/2695110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758062$0A5AB2E7-4491-4AC0-801B-03ADDCA655EF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6aea201e62712fc3bcd20109d84f91d847fc7078","datavalue":{"value":{"entity-type":"item","numeric-id":506967,"id":"Q506967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758062$50BF8637-98D3-4DA9-9CAB-21345E48E76C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a2543a8eaf8fe550d37175fe8c637171bfcfa8be","datavalue":{"value":{"entity-type":"item","numeric-id":1850500,"id":"Q1850500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758062$7C7CE07D-ACFE-4536-8B2D-7D76D0B0A8F4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"89979698039692d8b30dd476805176a82a96347c","datavalue":{"value":{"time":"+2002-06-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2758062$9B798E8C-15BE-423D-BF69-2F619CAD8389","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a813b4bdb99e25945b5eea647242a11d10dedf0a","datavalue":{"value":"03C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758062$F4448995-1144-4610-AB6E-B2B18ACD8DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758062$DA4227B6-DE00-4904-96BA-ACEE2DCC5BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758062$03453336-EE0A-4AC0-B53C-D92F7763C947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3dad0277bcd0256d3dcda33e7f0f7f7c58bb6096","datavalue":{"value":"03C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758062$9041E63D-2031-4F12-8BE7-2803009D462F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758062$85B79A74-87E0-4B28-A5FE-00148F93F1AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758062$99BB469C-594F-4F1E-95DE-7B9237F753A4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fba9c92f50070c29fc1398280b71b00dacf3640f","datavalue":{"value":"1679335","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758062$C3170AA1-ADA4-4EB1-9404-2E38FD5FD46C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be93bb5209f2d280e0eb153eccc5c0287d0e4b80","datavalue":{"value":"universal structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758062$49832B68-B30A-457E-8307-9CBD1EDC467B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea3ca956cc2fb403e1afc3f8aea11f2c5a829182","datavalue":{"value":"forbidden substructure","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758062$6D66C353-87F3-4414-A006-5454EDB3B08B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddc14051a93e8c78a1da682d6f4184d91e9c6088","datavalue":{"value":"graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758062$B8970558-A032-46BF-A7B9-7EFED5D4DC20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e6a8824b92c9436045429a61b8364839294d64c","datavalue":{"value":"colored graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758062$F0C2B2FA-B9DB-47A0-AD3A-016679995517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e739df749d6c867acd2763fc312bf2853a82972b","datavalue":{"value":"universal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758062$D343BBEB-686E-417B-86AF-EA00E22278BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1db4e3cd8c6237e3b25098b483a3ff821c3b321","datavalue":{"value":"forbidden subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758062$DDB5CEFF-49DD-4AE0-8D03-015AEF6C86C3","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":"Q2758062$D508F60A-4FF9-426F-9588-2E18308AD4C5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"30ceca149de9d70a293b3773b42fe44fa2da209f","datavalue":{"value":"https://doi.org/10.2307/2695110","type":"string"},"datatype":"url"},"type":"statement","id":"Q2758062$F8B55E8F-10A3-4A4F-B1DF-B6F32F30FA24","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6b4772c0adb383db8f774135b9927fe7442ebbe5","datavalue":{"value":"W2159942286","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2758062$C3A66C1A-B5EF-4761-BDCE-17C251B36D3D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"40ee6b4e0c810fb16f22fc8a003dd3e0b1743e2b","datavalue":{"value":{"entity-type":"item","numeric-id":1119949,"id":"Q1119949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758062$23A465CA-D9C2-43D0-A40C-823C532F8264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eda2db14c950cfacb2d9bab387b35d1aadfc67b0","datavalue":{"value":{"entity-type":"item","numeric-id":3284606,"id":"Q3284606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758062$EBD8D27A-691A-4011-83B7-331A370BCEB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5939592310ae494544d5841d15f42ab845d528d","datavalue":{"value":{"entity-type":"item","numeric-id":1191925,"id":"Q1191925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758062$A53A1A87-5394-41A2-A463-74765BC1C34A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c6443fdf4278b20d1f5bd6905a4b7b78b9f5810","datavalue":{"value":{"entity-type":"item","numeric-id":4875691,"id":"Q4875691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758062$F9BA2905-C861-4DE1-A220-EBBF01AB0089","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5a9691df3749f2125edb5d7ac13b8a5670d4fc0","datavalue":{"value":{"entity-type":"item","numeric-id":1293133,"id":"Q1293133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758062$E0A5F8B6-C039-45C8-845C-CEE61E338F0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ccf28283eeb22496da8d3fd142877510486e613","datavalue":{"value":{"entity-type":"item","numeric-id":4337505,"id":"Q4337505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758062$0DBCD66E-9358-4336-A95D-744CBA438D80","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cd9ebe56ec423ec5335930a0b1a45ca7ae3b5c0f","datavalue":{"value":{"entity-type":"item","numeric-id":6768298,"id":"Q6768298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758062$23A0422F-6F11-4D13-97B5-AA1633DDF179","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"096c461bef40b44bd22e570142a4857ab4da50b8","datavalue":{"value":"For a finite set \\(\\mathcal C\\) of finite structures in a finite relational language \\(L\\), the following problem is considered. Let \\(K\\) be the class of all countable \\(L\\)-structures which do not embed any structure in \\(\\mathcal C\\). Is there a universal structure in \\(K\\), that is, a structure in \\(K\\) which embeds any structure in \\(K\\)? Here one can consider embeddings either as strong embeddings (that is, preserving both \\(L\\)-relations and negated \\(L\\)-relations) or as weak embeddings (that is, preserving only \\(L\\)-relations); so there are two slightly different questions. Earlier the problem was considered for various classes of graphs with forbidden subgraphs. Usually there is no universal graph of the desired type; however, for some sets of forbidden subgraphs the existence of a universal graph had been proven. The authors consider the following decision problem: for any \\(L\\) and \\(\\mathcal C\\), determine whether \\(K\\) has a universal structure. The main result of the paper is that the decision problem is equivalent to the corresponding problem in the category of graphs with a vertex coloring by two colors. Moreover, the decision problems for strong and weak embeddings are shown to be equivalent. It is not known whether the problem reduces further to the category of ordinary graphs. It is also not known whether these problems are decidable; the authors feel that they may well be undecidable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2758062$93793556-7662-48DE-B6F0-B2741C9AB1D3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7a760754899c4252076421c1bbdd70a575016d7","datavalue":{"value":{"entity-type":"item","numeric-id":593287,"id":"Q593287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2758062$1C40AB1C-E909-47E8-9504-2C0192906F87","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"784b439e8576079e443417d9be189d4d11c8a91d","datavalue":{"value":{"entity-type":"item","numeric-id":4337505,"id":"Q4337505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"419d008a664bbc978359d14c2a87ae9aadb0dd25","datavalue":{"value":{"amount":"+0.8224075436592102","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":"Q2758062$A9C1C5BA-AE49-41DE-A587-CB846BCF4307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"982e3a392742b5d41d20cee49b322f43bd853325","datavalue":{"value":{"entity-type":"item","numeric-id":4410021,"id":"Q4410021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"419d008a664bbc978359d14c2a87ae9aadb0dd25","datavalue":{"value":{"amount":"+0.8224075436592102","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":"Q2758062$092A78DD-E996-4DF3-B8C1-8FC11D9F4A22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"658814ae5872adbf60e0685e20e9cb368413bad7","datavalue":{"value":{"entity-type":"item","numeric-id":875935,"id":"Q875935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eda7badc0f5456af8ad7240679da03bff350e7bb","datavalue":{"value":{"amount":"+0.8104045987129211","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":"Q2758062$5FDA6D2D-971E-45A3-B940-539447A6A952","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b34bc330eeb83eb8c7c81a28b42b16001b5e22c","datavalue":{"value":{"entity-type":"item","numeric-id":1293133,"id":"Q1293133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41eb4ba4cf3a18d350f5f01bb5dcd8b6ad436ad7","datavalue":{"value":{"amount":"+0.7818719744682312","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":"Q2758062$49864FE8-0262-4C15-AE19-E8F9E1147EDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e64f69bef2f7694c40b2542da3a5fac98aacb842","datavalue":{"value":{"entity-type":"item","numeric-id":2275384,"id":"Q2275384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41eb4ba4cf3a18d350f5f01bb5dcd8b6ad436ad7","datavalue":{"value":{"amount":"+0.7818719744682312","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":"Q2758062$8864F26F-1E27-4962-9540-39811A584A20","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Forbidden subgraphs and forbidden substructures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Forbidden_subgraphs_and_forbidden_substructures"}}}}}