{"entities":{"Q1333335":{"pageid":1344074,"ns":120,"title":"Item:Q1333335","lastrevid":43035873,"modified":"2025-07-17T02:46:37Z","type":"item","id":"Q1333335","labels":{"en":{"language":"en","value":"The complexity of infinite \\(H\\)-colouring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 638656"}},"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":"Q1333335$6D98659F-BE09-4093-B8B3-D436667A3CF8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a0769c16bd612fe1b552671e11f37a334575a880","datavalue":{"value":{"text":"The complexity of infinite \\(H\\)-colouring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1333335$585905C7-537D-47A3-B02B-2F44069261E2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9cbbdfe2c21fd66dfd953a64d9ea600812469486","datavalue":{"value":"0802.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333335$612C8F31-9183-4C17-B204-0F32B4FAE7B4","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":"Q1333335$04D57D7A-CD11-459B-9E26-ABC046BB076F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"82bd72124ae9a1c309abc4c30d0c3523c1c49e97","datavalue":{"value":{"time":"+1994-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1333335$BE9958D9-DD48-49F0-9FD3-B29302FBF903","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"18ca58b606e397c476ce802218aa12b452765306","datavalue":{"value":"For a fixed graph \\(H\\), the homomorphism problem for \\(H\\) is the problem of determining whether or not there is a homomorphism of a finite input graph \\(G\\) into \\(H\\). We investigate the complexity of this problem when \\(H\\) is allowed to be countably infinite and show that there exist recursive graphs with unsolvable homomorphism problems, as well as recursive graphs with solvable homomorphism problems of very high complexity. In fact, we show that there exist graphs with arbitrary recursively enumerable degrees of unsolvability.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1333335$6C6582BE-0DE9-455D-AAA2-60E2FC37CC48","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333335$4DD24C53-BE58-4839-B503-C70BA572ACD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333335$B52373A9-3F5B-4837-9B5D-D3ABED02B5E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333335$A7AE7002-9E56-43F4-A176-1C29097A9026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333335$2531B595-6C46-43CB-85E2-F9DD7BF0FD05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333335$E4323EA9-1378-49CC-9BD8-A2E394855B1B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8788c5c3c76773171eed0119fc2c0168dce899f3","datavalue":{"value":"638656","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333335$04F6B38C-DD5E-41D9-AD84-63C1EB5BFD86","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1333335$0CFC529F-99A3-4882-8B4A-73C574D8DE39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba079257fc8645ae49d5b08700818574d638ac16","datavalue":{"value":"recursive graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1333335$13B70D13-9BA1-40EE-82E6-777EB07DB2B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1333335$1DFBD36A-09B8-4694-BBD5-5460A3882F8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50019eaff869d05eee5ca71292ad7aeb5c989ac2","datavalue":{"value":"recursively enumerable degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1333335$1E993F12-8843-4A12-A1D2-26347DB32635","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"97c074488a992796954051150fc848867758ead2","datavalue":{"value":{"entity-type":"item","numeric-id":186265,"id":"Q186265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1333335$14EEEC9A-EAF1-4E82-AC9B-3942111BF95F","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":"Q1333335$A3EC3094-572A-4E6A-9891-117EB9183B93","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e4babab9052746ed8f992e8a00bb3e06edefbfbe","datavalue":{"value":"https://doi.org/10.1006/jctb.1994.1040","type":"string"},"datatype":"url"},"type":"statement","id":"Q1333335$58CE527C-CD40-4BF1-9E91-E8AF57E9C866","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5020268ea42d18a3c2a81548ae1e663e62dde0c5","datavalue":{"value":"W2039793369","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333335$CB74DAB4-F599-4EC1-B0D4-71A1BC8326CE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d51c03cdc5051844c54ed6e33f6bb44213d8994b","datavalue":{"value":"10.1006/JCTB.1994.1040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333335$5ED4E49B-228D-4B71-B625-DF66EDD0E626","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aae131b8b2ba59cb8f9fe6f97ab17a8d0c89046e","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbb84e6cd620cd88f7098752b27c4928572a3bc2","datavalue":{"value":{"amount":"+0.93068886","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":"Q1333335$94C43343-DA5A-4B6E-9AE5-0F536C68731C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d80436a7f2f690412ffc3c00684c219eb54ee6e","datavalue":{"value":{"entity-type":"item","numeric-id":3758852,"id":"Q3758852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbb84e6cd620cd88f7098752b27c4928572a3bc2","datavalue":{"value":{"amount":"+0.93068886","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":"Q1333335$FBA69F16-7EA5-4B87-BC2A-72592A5DF50C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e90b7693f6e777b9d04274ab936d34ef392baf75","datavalue":{"value":{"entity-type":"item","numeric-id":3139749,"id":"Q3139749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd3bbbcdc3dd74414e2a3c8e3126f35e3ae95497","datavalue":{"value":{"amount":"+0.9275342","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":"Q1333335$CB03E505-B730-47AD-95F2-D5A61C05EB71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0d139165441677c886138e6968d6793b7d61e73","datavalue":{"value":{"entity-type":"item","numeric-id":2184689,"id":"Q2184689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ded34e16a7d74cf33c5fbb5026d7755bb24ea68","datavalue":{"value":{"amount":"+0.9139453","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":"Q1333335$AEBB27FD-976B-4991-8CF2-963887F20F0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b164218765f44b5ac28050552e320a4ecd77dde","datavalue":{"value":{"entity-type":"item","numeric-id":4414491,"id":"Q4414491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49552feefd39099768eb16376ebac68d06593847","datavalue":{"value":{"amount":"+0.91334665","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":"Q1333335$45BC5148-6983-46F5-8B44-5825BD1C11AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21a806b0db9850ea4b003f6d7615ffca9b87d3ed","datavalue":{"value":{"entity-type":"item","numeric-id":2300155,"id":"Q2300155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a22a766d07022a127132120dc232848e5814c01a","datavalue":{"value":{"amount":"+0.91178775","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":"Q1333335$A07FBFAC-623E-4440-B356-07C1B3E32FDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e15b3490248d790e7bd1f31c7e59e49c448d05b1","datavalue":{"value":{"entity-type":"item","numeric-id":5427831,"id":"Q5427831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39b0e6692cea64127f781e5bfb1cd98c705bb8a5","datavalue":{"value":{"amount":"+0.9084361","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":"Q1333335$2AC730BA-42C0-4619-A119-8B49943F2502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"068de292421424c3d0dbafa52cc761b8d5bd08d9","datavalue":{"value":{"entity-type":"item","numeric-id":1579552,"id":"Q1579552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6f4b939a9e0c8f78f5d0189416926bfea28a006","datavalue":{"value":{"amount":"+0.90810555","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":"Q1333335$BF2D55E7-CBA0-41AB-911A-CC23DB62E575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f80d83cca425f75111c17ade4496e751f78e3cd","datavalue":{"value":{"entity-type":"item","numeric-id":4520430,"id":"Q4520430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23fd98710d32b05e96f4decc2c9503bf4743457a","datavalue":{"value":{"amount":"+0.8969037","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":"Q1333335$ED76EAED-7185-4DDC-9C80-C02964B378F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d36d2984c1b67ec0e6ee06ccaebdad0b82b69bc","datavalue":{"value":{"entity-type":"item","numeric-id":1045065,"id":"Q1045065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a0654dbc04e4cae369a78ed1a99657f0ac9d766","datavalue":{"value":{"amount":"+0.89645404","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":"Q1333335$AD95388F-600D-4454-82C0-3924DD8C6E38","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1333335","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1333335"}}}}}