{"entities":{"Q579241":{"pageid":581008,"ns":120,"title":"Item:Q579241","lastrevid":62922894,"modified":"2026-04-11T09:00:42Z","type":"item","id":"Q579241","labels":{"en":{"language":"en","value":"Graph colorings and recursively bounded \\(\\Pi ^ 0_ 1\\)-classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4014694"}},"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":"Q579241$FC9FAF06-421F-4A5F-A3AB-21501AD768D4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6158f352fef733f64ade4eba9d1178fa070887ee","datavalue":{"value":{"text":"Graph colorings and recursively bounded \\(\\Pi ^ 0_ 1\\)-classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q579241$3810BFE5-D232-40EF-A033-75B8F279DE9A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"12e90ab3d52ca7eb44273af1e2585b3155f92692","datavalue":{"value":"0625.03024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579241$285F2359-86EA-4F36-9039-CF478DCC25F2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cbf30a08ab6b753f6cdc4c4c0ff523fab070c57b","datavalue":{"value":"10.1016/0168-0072(86)90051-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579241$A1157C33-4448-41E5-8DA4-E60374E3431E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$D13C5D27-B8E8-4A4E-B215-F0BF864411C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q579241$19EDC1E0-B81C-4A27-9BF4-2B8915D2BCAD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a1ac97fcc67a72fd5bc3f11ece4a9695b9c8c663","datavalue":{"value":"Bean showed that the k-colorings of a recursive graph is always a recursively bounded \\(\\Pi^ 0_ 1\\)-class. The main theorem of this paper proves the converse of Bean's result. That is, we show that for any recursively bounded \\(\\Pi^ 0_ 1\\)-class \\({\\mathcal C}\\) and any \\(k\\geq 3\\), there exists a highly recursive graph \\({\\mathcal G}\\) such that up to a permutation of colors there is an effective 1:1 degree preserving correspondence between the k-colorings of \\({\\mathcal G}\\) and the elements of \\({\\mathcal C}\\). We also discuss other combinatorial problems whose solutions are recursively bounded \\(\\Pi^ 0_ 1\\)-classes and the possibility of their representing an arbitrary \\(\\Pi^ 0_ 1\\)-class.","type":"string"},"datatype":"string"},"type":"statement","id":"Q579241$C2EBD5EC-2172-4BC1-A65D-45A3C24507CC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579241$C359552B-789B-43FF-9C3C-64C01DECA8A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579241$8EF5BF15-01C9-48E3-8947-7E9282FE539F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1e30dfb950db9974663803a738f55fb626a5b3be","datavalue":{"value":"4014694","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579241$726E4AFA-DE62-4856-97B6-5A7FDD678146","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29ffc323f8f312cf79efaa5fd76c8005712ca950","datavalue":{"value":"recursive graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q579241$7F8099D2-08BF-4264-A887-6DF68FC450C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29cf83eb71a98478a15be1445592e8b3e8506e5c","datavalue":{"value":"k-colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q579241$7ECFD6A0-63EB-4E43-9C5C-7A46013FEDAF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5dc30c87ee90e636f091c198a5b55721665c69f9","datavalue":{"value":{"entity-type":"item","numeric-id":698606,"id":"Q698606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$6317FE14-EE58-4BD1-805A-44D551C1CD95","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":"Q579241$C6DB0586-A281-47C3-8180-6256AA736E38","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ca09e3e7f81760379b758fb507211b10cd2651c3","datavalue":{"value":"https://doi.org/10.1016/0168-0072(86)90051-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q579241$1772D731-392D-4897-98AE-9D4845827B58","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"121eb23c15653f05016059159c35b1dabb7ee215","datavalue":{"value":"W2091918101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579241$74E907A0-FFC2-43F3-9D85-CD0B6BBCCA80","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"55b9ff904e1c98a6431855b40a7e673c55670f79","datavalue":{"value":{"entity-type":"item","numeric-id":4097267,"id":"Q4097267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$514E11E9-FEA2-473F-BB3F-E0627AE58906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eccf8297d0c1fba4465ce0e38070ebe79a553a60","datavalue":{"value":{"entity-type":"item","numeric-id":4091988,"id":"Q4091988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$68BA0FEB-EA6A-433E-84EC-CE352AAEF928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"007c64cb1e51e420a82b1528582743678952b922","datavalue":{"value":{"entity-type":"item","numeric-id":2648578,"id":"Q2648578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$3EB77B71-4B70-440B-832A-90F9E01DE578","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf67e5c77bdefcc878c1a3ad7fdf95f68a51bea3","datavalue":{"value":{"entity-type":"item","numeric-id":2534881,"id":"Q2534881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$F262D302-41EE-4F05-A008-6C326E9392D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86108cb677c98bb6850d4621a5c75e6c35903675","datavalue":{"value":{"entity-type":"item","numeric-id":5677474,"id":"Q5677474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$37CB61CF-A7A0-406D-B2EA-B18812B39724","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"238fd29f8ac226411b59375cbcf60013cf861c4c","datavalue":{"value":{"entity-type":"item","numeric-id":2543461,"id":"Q2543461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$51551C4B-2E93-493B-8BF2-9D91CE38698A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de43f3e978a9ce24db65e773f8fff3d02c7dc139","datavalue":{"value":{"entity-type":"item","numeric-id":3944587,"id":"Q3944587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$6EB6F846-A4D5-4194-AB17-44626196E04A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0091e4a6d73f3357e07e72a0e261ba81111ea79","datavalue":{"value":{"entity-type":"item","numeric-id":3907590,"id":"Q3907590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$30FA7826-5D79-4DDB-9592-C8B53B0864D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b686b6561b404abd99050b38d4f468b71b973a86","datavalue":{"value":{"entity-type":"item","numeric-id":3950561,"id":"Q3950561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$B4587172-7677-43D2-ADE2-B002DA2A3EDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"053ffe8d65e0994d475a368e3c3296b25479e09b","datavalue":{"value":{"entity-type":"item","numeric-id":2266723,"id":"Q2266723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$753BBF15-087F-4AC8-843F-61A2CFE23886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0682f1635aec93c2234093490373e739c3b48f65","datavalue":{"value":{"entity-type":"item","numeric-id":5663873,"id":"Q5663873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$9EC2EE43-EEEF-42B7-A845-77EF824B7919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a057cb680d03d556a552e031e992c3bc06678b7","datavalue":{"value":{"entity-type":"item","numeric-id":5181352,"id":"Q5181352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$22FA8974-A956-4275-A8B7-462EB2413172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bd6a332047a8ed38533aaf34e031ea50ce95b50","datavalue":{"value":{"entity-type":"item","numeric-id":3955342,"id":"Q3955342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$7392A282-8DD7-47D4-8AD3-E1384893AB70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$1F69B1DA-2E62-469A-880F-FD601DF3E48A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f47f7850801654ea9993f2f197d1fde75c0c53d","datavalue":{"value":{"entity-type":"item","numeric-id":4175305,"id":"Q4175305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579241$5F776366-FF3B-4E83-A402-D8A7B390D28D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef1a4d67ccd572931990f028bfb7b90a2672b94b","datavalue":{"value":{"entity-type":"item","numeric-id":4844508,"id":"Q4844508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bea5b3280b663230d5269472e869a142361b6e6","datavalue":{"value":{"amount":"+0.8104207515716553","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":"Q579241$4FA26D41-4EBE-4C0B-A4E2-9FF26BFEEFA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a98ee6b5a94194f7f311308db7b64d8c4ff0e8b","datavalue":{"value":{"entity-type":"item","numeric-id":686481,"id":"Q686481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bfeea0bf91183f4a6231ad812af7870e5582012","datavalue":{"value":{"amount":"+0.8098567724227905","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":"Q579241$EA3CC9C4-10F3-4FD8-A010-694EE5235326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc8b4a7f190f8101a14edb1aac10ca2df289d570","datavalue":{"value":{"entity-type":"item","numeric-id":4249723,"id":"Q4249723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a85dbc367f5e1cac07753b6946934d6f29d2d6c","datavalue":{"value":{"amount":"+0.798835277557373","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":"Q579241$93B134A9-3ED0-4825-8CE7-ECB0FB1017C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f67d644de3f5bbeb92997c88bbc9ce39c5374bd","datavalue":{"value":{"entity-type":"item","numeric-id":4249728,"id":"Q4249728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"015978db5f0ab4eca747d938e4a14585cae7d555","datavalue":{"value":{"amount":"+0.7959315776824951","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":"Q579241$D5E04500-F7CB-4FA8-B594-89583E72EBA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f47f3eacb8e35af3a43135f7dc88c7216b319dd5","datavalue":{"value":{"entity-type":"item","numeric-id":1295384,"id":"Q1295384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55dda4ffbdf53955b7f8edeb97ddd3fdd4583b1a","datavalue":{"value":{"amount":"+0.7833471894264221","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":"Q579241$B2EB5A78-F0DA-48EA-8A7B-26F92D6CE1C3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph colorings and recursively bounded \\(\\Pi ^ 0 1\\)-classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_colorings_and_recursively_bounded_%5C(%5CPi_%5E_0_1%5C)-classes"}}}}}