{"entities":{"Q612947":{"pageid":614723,"ns":120,"title":"Item:Q612947","lastrevid":63050406,"modified":"2026-04-11T10:05:43Z","type":"item","id":"Q612947","labels":{"en":{"language":"en","value":"Building graphs from colored trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5827410"}},"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":"Q612947$A63A5587-5948-47A1-86AF-7D1804B7C719","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d3268b1e77d93c13afc407f2d2edb43c62411579","datavalue":{"value":{"text":"Building graphs from colored trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q612947$2D81686D-F83C-434B-8B83-A3AC268A7250","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"322c1c2310157b4d91c589974521cd1a9f6ac5de","datavalue":{"value":"1204.05091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612947$0C7ECDAB-61EA-4C44-B2A9-160155E67F0E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c229d7026cd809959f7c6e01c232d7bad4c4c490","datavalue":{"value":{"entity-type":"item","numeric-id":612946,"id":"Q612946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q612947$ECA29133-459C-429E-B774-0BDDD3CDB5A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ed046cfa0f3aaebe7ee5a321838d2b14a94a270","datavalue":{"value":{"entity-type":"item","numeric-id":221782,"id":"Q221782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q612947$198AE8F2-5DCE-48ED-83FC-BDE062118775","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q612947$D286544A-183E-420F-B994-030E3DA5FA0F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63d0db48794e6800d8c22359b1f6c876c0e4d309","datavalue":{"value":{"time":"+2010-12-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":"Q612947$06B63307-9C5D-421A-9AE5-589DCCD2C40A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"225c7af7fa2737b4d82a26d3dc10c002115e9299","datavalue":{"value":"https://eudml.org/doc/230737","type":"string"},"datatype":"url"},"type":"statement","id":"Q612947$AEF96989-70CC-4C11-9D20-C3AA4F110B39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"7dca785704ac2dc98a65297cfa172c3741a39d7c","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r161.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q612947$2F1294E4-1DF2-42C6-9393-6F29D8A123BD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bb3c508d47439f7b21f6ae428c358db253aceec4","datavalue":{"value":"Summary: We explore the computational complexity of satisfying certain sets of neighborhood conditions in graphs with various properties. More precisely fix a radius \\(\\rho\\) and let \\(N(G)\\) be the set of isomorphism classes of \\(\\rho\\)-neighborhoods of vertices of \\(G\\) where \\(G\\) is a graph whose vertices are colored (not necessarily properly) by colors from a fixed finite palette. The root of the neighborhood is the unique vertex at the ``center'' of the graph. Given a set \\({\\mathcal S}\\) of colored graphs with a unique root, when is there a graph \\(G\\) with \\(N(G)={\\mathcal S}\\)? Or \\(N(G)\\subset{\\mathcal S}\\)? What if \\(G\\) is forced to be infinite, or connected, or both?  If the neighborhoods are unrestricted, all these problems are recursively unsolvable; this follows from the work of \\textit{V. K. Bulitko} [Tr. Mat. Inst. Steklova 133, 78--94 (1973; Zbl 0295.05124)]. In contrast, when the neighborhoods are cycle free, all the problems are in the class P. Surprisingly, if \\(G\\) is required to be a regular (and thus infinite) tree, we show the realization problem is NP-complete (for degree 3 and higher); whereas, if \\(G\\) is allowed to be any finite graph, the realization problem is in P.","type":"string"},"datatype":"string"},"type":"statement","id":"Q612947$60C230F4-6836-4E47-A7C2-E746DF7F0CCC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612947$52BD60CD-71F3-4EAC-AC4C-78FFD4F6AAD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612947$C7AAABEE-C323-4C93-9216-A250479ED658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612947$417317ED-6BE0-4D74-8D87-568A3D1B610A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1229c8c1e965faedfd5dae3e2b9d1159c68da4b9","datavalue":{"value":"5827410","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612947$133451EF-BE5A-43DC-B70C-F57C3897BDDF","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":"Q612947$A6EB7C2F-34D3-4FDD-9AFF-27F58BBB36B1","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"f4994c819702596aefa6f86ca67b0e6924000d4e","datavalue":{"value":"bafkreibahvd4zjzaupuxoiiwu5l76be6hvrvc6i63h7umwhmumlwl5x2wq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612947$ECC1C65A-97A0-456B-A6DC-ED12A29F0900","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"913c3078f9c22c974f8ac41770455b6da4414537","datavalue":{"value":{"entity-type":"item","numeric-id":5897560,"id":"Q5897560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11a8a84d17c970ed496bc4108c9df71afb121b10","datavalue":{"value":{"amount":"+0.9044493","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q612947$893F0FF0-E965-4F65-8CFC-9328B8A0C46D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7262d033d9fcbf27c58de9742dfc5af48ac809b8","datavalue":{"value":{"entity-type":"item","numeric-id":1686264,"id":"Q1686264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b08b0e3a53ad3d6f093907c16e346b10f516073","datavalue":{"value":{"amount":"+0.89562523","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q612947$3FC6D5BA-299B-49E0-8151-37A8B05A0BA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38b759daad87bec33c15df1acd097a66eb85561c","datavalue":{"value":{"entity-type":"item","numeric-id":1363645,"id":"Q1363645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50a6d7e441cfc7a38fbf907f7928ec67020f5bc3","datavalue":{"value":{"amount":"+0.8899722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q612947$AB7A6EE4-496C-4F8E-99BE-2F6EAE16FDB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f080b5087a24af7aa5207003b0c9625273695eae","datavalue":{"value":{"entity-type":"item","numeric-id":4281630,"id":"Q4281630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50a6d7e441cfc7a38fbf907f7928ec67020f5bc3","datavalue":{"value":{"amount":"+0.8899722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q612947$4483DBF3-9DDD-4B16-80F5-4C58893CFC01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e70c7425dd28647a4990221155adbea99a066371","datavalue":{"value":{"entity-type":"item","numeric-id":5904060,"id":"Q5904060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84700c4b7d5add8f3e80c81f43dcdafb50528635","datavalue":{"value":{"amount":"+0.8847676","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q612947$CE507DEE-F102-4378-81B0-338B87D10D10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8be43a96da948f9ddd372d8645120ec3ea57ebbd","datavalue":{"value":{"entity-type":"item","numeric-id":5898715,"id":"Q5898715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"286caa63a9e981579bed59fc1ef7fba040f6ac79","datavalue":{"value":{"amount":"+0.88476753","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q612947$B0747E49-656C-48C1-954C-379F1B4FC912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5b4fffd3b9ba6a6d43f9f39c5da29b2d20db7f0","datavalue":{"value":{"entity-type":"item","numeric-id":1918569,"id":"Q1918569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc8d4d9cb9d59928ed6d5049429ff43f27aae936","datavalue":{"value":{"amount":"+0.8832737","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q612947$9EDBF7F3-5B32-486B-9D59-B84741004C17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"125e0e1bda8bf2098b7b6108491b3195c93d9739","datavalue":{"value":{"entity-type":"item","numeric-id":3094945,"id":"Q3094945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"817387ca2a9ea8757acda16a43721e24d5f114f9","datavalue":{"value":{"amount":"+0.88232374","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q612947$2E8BA00E-5197-467A-B2FF-27EEFAF09A8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d310ed37ce3a7d357d30f73540be04a3428765bc","datavalue":{"value":{"entity-type":"item","numeric-id":2279275,"id":"Q2279275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"980e452e703c995b21296e563d01f64a52753320","datavalue":{"value":{"amount":"+0.8818295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q612947$5BB5C811-9943-49A6-A44B-675990A2B7BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9ad9475ad01eafde9fb73e9c56601e871d4faf2","datavalue":{"value":{"entity-type":"item","numeric-id":2654597,"id":"Q2654597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4fff70608efe3391dd7b0d6d57b1e05faf85259","datavalue":{"value":{"amount":"+0.87865686","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q612947$2022AA26-2392-4E5F-864E-3886F007400C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Building graphs from colored trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Building_graphs_from_colored_trees"}}}}}