{"entities":{"Q5963197":{"pageid":8139999,"ns":120,"title":"Item:Q5963197","lastrevid":102148463,"modified":"2026-06-06T03:36:34Z","type":"item","id":"Q5963197","labels":{"en":{"language":"en","value":"Reverse mathematics and the coloring number of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6550118"}},"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":"Q5963197$C703E96C-F4DF-4AAB-8874-3B195692FBFD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"352877f563fd3662779d7de7c16b2ab9cda58b7e","datavalue":{"value":{"text":"Reverse mathematics and the coloring number of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5963197$B07F0F9A-D18C-47E3-8BB7-0AE5758E8B85","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"026aa24538ce80798214987aa73aefd4b9fcdd78","datavalue":{"value":"1353.03008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5963197$AF75E58F-C47D-4054-843F-B1794AFD1E74","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bdecb0dda3e794a076c2107ebd2f4e6fef837e80","datavalue":{"value":"10.1215/00294527-3321905","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5963197$0E251B42-0A11-4787-8C6B-A9CD7065F100","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8cbe2666989e7ba412ce9370390d3b473c23358","datavalue":{"value":{"entity-type":"item","numeric-id":246756,"id":"Q246756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5963197$BE0C54E2-AE84-4342-AFD8-3307BC2A3266","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6325d9f59cde8ebbdb24a9f950cab3fcef3decf6","datavalue":{"value":{"entity-type":"item","numeric-id":190248,"id":"Q190248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5963197$D024BFAF-77A1-44F6-8B82-B20D1648C803","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9baa329984daf997c3bf5a084a91839bc1428d33","datavalue":{"value":{"time":"+2016-03-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5963197$4A50EC4B-8925-474A-A53F-CF049DE0CEF2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8c264a277af8f231dc5fc35905f2dafa917c7067","datavalue":{"value":"https://semanticscholar.org/paper/5f4c95625aa455cdf0af3bdc6a2cd970d9b02bac","type":"string"},"datatype":"url"},"type":"statement","id":"Q5963197$D3EE2326-AE93-4797-AB56-6E94FFC4A1D8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c2c7a0f70c0b7cc2161585e985e86183cb70d3ef","datavalue":{"value":{"entity-type":"item","numeric-id":335001,"id":"Q335001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5963197$AF0CC514-CB4C-462D-94E1-2D9F3630538A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"13841f0b96793f178ce9a7dcac9f232220625aee","datavalue":{"value":"03B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5963197$1771011F-106E-4936-A705-A937CC48A5FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4cb4544bfd0397cd4a315ee326499c372f013de5","datavalue":{"value":"03F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5963197$6CED8774-3B97-418A-8892-919CCA64D349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"758b4d196a1f97708f26591fee42c00739e26cc0","datavalue":{"value":"03D80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5963197$A73D86B3-09CC-4FC2-A5AF-41A5C655EEF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5963197$A60F9779-C410-4B35-AF0D-7EA06DBC8121","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7c7b7529ca769e655161de41fe36cb38e408fd38","datavalue":{"value":"6550118","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5963197$CB7DEC04-1164-47A0-994F-F84A8078F07A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e325a72f0e26ab98b1e996e2e86ac8d7891b9a92","datavalue":{"value":"reverse mathematics","type":"string"},"datatype":"string"},"type":"statement","id":"Q5963197$17A6FF3C-C237-4580-93E7-5C76A0439220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fb84118c511a2f29d9e1aa1fd7ab159cc59e7c6","datavalue":{"value":"coloring number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5963197$B169D023-1302-403E-B7DD-2208F873AC22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddc14051a93e8c78a1da682d6f4184d91e9c6088","datavalue":{"value":"graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5963197$261AD28C-F6B5-4867-9691-70B317C9E3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f401dd9c1f566772595ae85ebc3ea4d1157a2c3d","datavalue":{"value":"computability theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q5963197$061425A2-A8C1-4DFB-8CD8-4CD16A3BF0EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8d8b1d67384cd642422b7e762b22af41307ae4c","datavalue":{"value":"recursion theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q5963197$E5F0CA78-343A-4A02-9C4B-DFB835F6BC48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"461d39200e573b893247f72bc707a68f4eb77ea1","datavalue":{"value":"ACA","type":"string"},"datatype":"string"},"type":"statement","id":"Q5963197$3A2CFA9B-EFFC-4441-A8ED-0882EAFFC8A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"971c3a87d61cd2b2dd145b9052225bdfe903feef","datavalue":{"value":"WKL","type":"string"},"datatype":"string"},"type":"statement","id":"Q5963197$4A69BE38-8EBF-45F3-9AE8-0CE1F9A3723D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8439c3c323b21d48b0e534a0ebe58f84d18c385","datavalue":{"value":"linear order","type":"string"},"datatype":"string"},"type":"statement","id":"Q5963197$0C8EB5B5-59A8-40AD-BE65-4079DD35A963","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":"Q5963197$B17E4AEB-5167-4284-9DFE-33807A206242","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"58a66a3e0b917e4eb3c26c72b6a2cd68f9a5961f","datavalue":{"value":"W142641161","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5963197$66E76B5E-A2B2-4E90-AF02-1C6DE6D99C80","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f83c76cdb40f73ec24f177699a129379f6ef374f","datavalue":{"value":"This article formalizes and analyzes the logical strength of some statements about coloring numbers of graphs using the reverse mathematics axiom hierarchy. If \\(G\\) is a countable graph and \\(k\\) is a natural number, we say the coloring number of \\(G=(V,E)\\) is at most \\(k\\) and write \\(\\mathrm{COL}_{\\mathrm{LO}} (G) \\leq k\\) if there is a linear order \\(\\leq\\) on the vertices \\(V\\) such that for every \\(v \\in V\\), \\(|\\{u \\leq v \\mid (u,v)\\in E \\}|<k\\).NEWLINENEWLINETheorem 6.4 of the paper shows that for all standard \\(k \\geq 2\\), WKL\\(_0\\) is provably equivalent over RCA\\(_0\\) to the statement: If \\(G\\) is acyclic then \\(\\mathrm{COL}_{\\mathrm{LO}}(G) \\leq k\\). Placing additional constraints on the linear order increases the strength of the related graph theoretic statements. Write \\(\\mathrm{COL}^S_\\omega (G) \\leq k\\) if the linear order is order isomorphic to \\(\\mathbb N\\) and \\(\\mathrm{COL}^W_\\omega (G) \\leq k\\) if for every \\(v \\in V = \\{ v_0 , v_1 , \\dots\\}\\), there is an \\(m\\) such that \\(\\forall n \\geq m ( v \\leq v_n )\\).NEWLINENEWLINETheorems 7.1 and 8.1 prove that ACA\\(_0\\) is equivalent to (1) if \\(G\\) is acyclic and \\(k\\geq 2\\) then \\(\\mathrm{COL}^S_\\omega (G) \\leq k\\), and also to (2) if \\(G\\) is acyclic then \\(\\mathrm{COL}^W_\\omega (G) \\leq 2\\).NEWLINENEWLINEThe paper includes numerous related results proved in RCA\\(_0\\) and many computability theoretic consequences.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5963197$BE9E1DC0-C87E-4E17-974E-49107DE79F76","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74faef0933e4d9644418ca445ec475d8acb15cfe","datavalue":{"value":{"entity-type":"item","numeric-id":4521128,"id":"Q4521128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1491641c2fae215d02dfc148d801a4d155eebc2","datavalue":{"value":{"amount":"+0.8362174034118652","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":"Q5963197$FCAC0D0C-2479-4722-A890-58BDC54231B8","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":"c1491641c2fae215d02dfc148d801a4d155eebc2","datavalue":{"value":{"amount":"+0.8362174034118652","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":"Q5963197$AF9B9C13-478B-49BB-B4A7-444FEB5F96F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fcf34acea7e91b715f055db96bf397c5b1e6a68","datavalue":{"value":{"entity-type":"item","numeric-id":2312088,"id":"Q2312088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a9150e154332e6a479b814a6ed4868bd3959510","datavalue":{"value":{"amount":"+0.8000380992889404","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":"Q5963197$A027FEC5-3079-475D-ACD3-FCF9D33AAA98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c248fab3d2b7d61b3558f086abea4f8db9e9595f","datavalue":{"value":{"entity-type":"item","numeric-id":4224080,"id":"Q4224080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4490d71e545f7d1e884343f97c36b341aec2731d","datavalue":{"value":{"amount":"+0.7993834018707275","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":"Q5963197$2DD67E05-ED65-40C1-8E8F-A5A2E475A544","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"427452204c92cd0968945b6765354539eee3a230","datavalue":{"value":{"entity-type":"item","numeric-id":3616350,"id":"Q3616350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4490d71e545f7d1e884343f97c36b341aec2731d","datavalue":{"value":{"amount":"+0.7993834018707275","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":"Q5963197$19AD6B55-BE71-4438-9923-EF3E7CC7C7A4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reverse mathematics and the coloring number of graphs","badges":[]}}}}}