{"entities":{"Q922525":{"pageid":924373,"ns":120,"title":"Item:Q922525","lastrevid":65434605,"modified":"2026-04-12T02:33:58Z","type":"item","id":"Q922525","labels":{"en":{"language":"en","value":"On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4168662"}},"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":"Q922525$FEE0108A-3A0C-4B62-AC0D-E66AA1EDE8A2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b243b80bf17981752d60198a84732e9ca744027c","datavalue":{"value":{"text":"On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q922525$FB8FD941-DA1F-47DA-8DAD-C1AB7B40A0EB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b4e7e4ad4b86863f5d89d0b3d771d521c42035e5","datavalue":{"value":"0711.03013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922525$E2EA9630-DC80-4177-941A-251B05804FFA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"826f8dc3202351b9d4f02bc0670c205c5ed175d4","datavalue":{"value":"10.1016/0168-0072(89)90037-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922525$A334F666-1C69-497A-81A2-068F20FDCBC6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0353358515be2d1b5877a1b267862980a7b952cd","datavalue":{"value":{"entity-type":"item","numeric-id":294935,"id":"Q294935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922525$A169B178-C279-4D6C-B8C9-7D252F7616F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d63fb644043f68eec80a16990f4f5c12af2bb809","datavalue":{"value":{"entity-type":"item","numeric-id":811135,"id":"Q811135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922525$2A9EDCE9-D625-4EC4-8EEE-D92E8112A878","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":"Q922525$76F3C9FA-3AB0-4485-A279-04AF7DFD41FD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q922525$46123617-59C9-40D2-99BC-16B013F5568E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"37392b0bf9b960e49b5f9124d33b8bf8c7e35582","datavalue":{"value":"[For Part I see ibid. 45, No.1, 1-38 (1989; Zbl 0685.03033).]    A recursive graph is a graph whose edge set and vertex set are both recursive. Although the chromatic number of a recursive graph G (denoted \\(\\chi\\) (G)) cannot be determined recursively, it can be determined if queries to the halting set are allowed. We show that the problem of determining the chromatic number of a recursive graph with a minimum number of queries to the halting set, is closely related to the unbounded search problem. In particular if f is a non-decreasing function such that \\(\\sum_{i\\geq 0}2^{-f(i)}\\) is effectively computable, then there is an algorithm to determine \\(\\chi\\) (G) with f(\\(\\chi\\) (G)) queries to K iff \\(\\sum_{i\\geq 0}2^{-f(i)}\\leq 1\\) (i.e., f satisfies Kraft's inequality). We also investigate recursive chromatic numbers (which require queries to a set much harder than the halting set, namely \\(\\emptyset ''')\\), the effect of allowing queries to a weaker set, and the effect of being able to ask p queries at a time. Most of our results are also true for highly recursive graphs (graphs where one can determine the neighbors of a given node recursively), though there are some interesting differences when queries to K are allowed for free in the computation of a recursive chromatic number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q922525$838CAF1E-5A05-434A-95ED-8919F1175AB9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922525$BD6D1248-2691-4114-A4B3-36FE590A8826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922525$484F6C7A-AC91-47F4-88A4-6F335A85AE8A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4babc8ad124f7908091d41247433b8f999dd8d51","datavalue":{"value":"4168662","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922525$19576B11-8985-406C-9C68-8ADA1E3E4E79","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29ffc323f8f312cf79efaa5fd76c8005712ca950","datavalue":{"value":"recursive graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q922525$54448D9A-03E2-4EA5-B78A-E4592E009D7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q922525$D6365B52-11E7-4EBB-B8AE-27C27841479C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"358dd5c58c70b6b4f5e68cf841415fc90fed267e","datavalue":{"value":"unbounded search","type":"string"},"datatype":"string"},"type":"statement","id":"Q922525$EC7D0142-E59A-4664-992D-3E06E4D540EA","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":"Q922525$411AF8F9-7E68-440D-8D45-D59B8FBA12BC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9344dd993e2c040cade89fdebd0ddbbc5bded295","datavalue":{"value":"https://doi.org/10.1016/0168-0072(89)90037-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q922525$B858A735-7A9F-42C9-874A-8F9F8F0A0E1D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"690029da6e479bb59bb00e4995d1085de668eee3","datavalue":{"value":"W4213194823","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922525$B424D171-AFFC-458E-9552-DB5103B585D9","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":"Q922525$A2513D12-A493-49C1-AFD3-C98D8BC8093F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b77f188fe72e43e201f9a479e931979a80d70190","datavalue":{"value":{"entity-type":"item","numeric-id":3476283,"id":"Q3476283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922525$8A8F4A57-2B60-44CD-B3E3-885CB6F6DBEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a896ba37c91e41236e1544cdb09d67b6666868a9","datavalue":{"value":{"entity-type":"item","numeric-id":1825865,"id":"Q1825865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922525$D02FD0A7-FB1B-47C2-9EC5-A4AD65657F72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"018038fb101d8ec315a3c155690ad0c57968b1f9","datavalue":{"value":{"entity-type":"item","numeric-id":1803657,"id":"Q1803657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922525$C2B9008A-D987-4911-B07F-A7A1C59853C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddd7cf5c3cf20a3faedc8fb513c29ca711e97cb6","datavalue":{"value":{"entity-type":"item","numeric-id":1229581,"id":"Q1229581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922525$D195B151-3898-403E-B1D7-71861BD6A2CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5803ff3145fb130a9bd533965de485d689cf81c5","datavalue":{"value":{"entity-type":"item","numeric-id":595648,"id":"Q595648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922525$9371EC06-04CC-41D5-B111-D9E2810E4149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f024f8820c524c134f0fa0b7424f0c84ae19c3d4","datavalue":{"value":{"entity-type":"item","numeric-id":5595624,"id":"Q5595624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922525$93ECDF26-E757-4EF4-99E4-9826E631A53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecdacd7d8076e20fd3633d5d758e618af67b3432","datavalue":{"value":{"entity-type":"item","numeric-id":3038630,"id":"Q3038630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922525$61541070-DF92-4D1A-B165-C5E5D6DBC7A3","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":"Q922525$831C9AE9-63CF-41F8-8352-0652E740F0E5","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":"Q922525$2F9D62C1-A2D9-4CE8-BC8D-CB6296A788B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15736a1fabe53e34c9adbd1c3f77269c133e2124","datavalue":{"value":{"entity-type":"item","numeric-id":4040892,"id":"Q4040892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922525$1E3F8473-F102-4533-9075-762BBBFE5F3B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a7add1a4076bda81856b86d2ef5ec0470eabacb","datavalue":{"value":{"entity-type":"item","numeric-id":1825865,"id":"Q1825865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3510ae1a12750bfcf1e4267ff020066c10b0224b","datavalue":{"value":{"amount":"+0.942096471786499","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":"Q922525$86E88B83-D123-4AF4-A09C-CD7E52D7B2F9","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":"7ee594e9f585a860f30b488ac9b87ebc1ca803dd","datavalue":{"value":{"amount":"+0.8559043407440186","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":"Q922525$EA5FB09F-AB5B-4440-BA49-4FE1763CEA6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fddbe434350ae64b858592d6e61ed693df4b165d","datavalue":{"value":{"entity-type":"item","numeric-id":5096341,"id":"Q5096341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab68bd376e20bcc619213a1d2a6ac7399e7adbe9","datavalue":{"value":{"amount":"+0.8370785713195801","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":"Q922525$659D07DD-28B0-46C3-9D6A-5ECDC60D8437","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":"6000582e19587d92901f7f10012792d65137bd81","datavalue":{"value":{"amount":"+0.8076990842819214","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":"Q922525$8B689EDF-BE96-4846-936E-316E3C51220E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c58d4b9e8132e9b873231b14592d4e7c41cc0c22","datavalue":{"value":{"entity-type":"item","numeric-id":1391302,"id":"Q1391302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44fdc966385763ba4e83cbf512a048e553f1b7a8","datavalue":{"value":{"amount":"+0.789469301700592","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":"Q922525$10427A2B-2B46-4D08-A4C9-D766F399800A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_finding_the_chromatic_number_of_a_recursive_graph._II:_The_unbounded_case"}}}}}