{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:38:39Z","timestamp":1777516719075,"version":"3.51.4"},"reference-count":15,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2015,7,1]],"date-time":"2015-07-01T00:00:00Z","timestamp":1435708800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2015,7,24]]},"abstract":"<jats:p>Abstract<\/jats:p>\n                  <jats:p>We study the reverse mathematics and computability of countable graph theory, obtaining the following results. The principle that every countable graph has a connected component is equivalent to [Formula: see text] over [Formula: see text]. The problem of decomposing a countable graph into connected components is strongly Weihrauch equivalent to the problem of finding a single component, and each is equivalent to its infinite parallelization. For graphs with finitely many connected components, the existence of a connected component is either provable in\u00a0[Formula: see text] or is equivalent to induction for [Formula: see text] formulas, depending on the formulation of the bound on the number of components.<\/jats:p>","DOI":"10.3233\/com-150039","type":"journal-article","created":{"date-parts":[[2015,7,26]],"date-time":"2015-07-26T09:13:47Z","timestamp":1437902027000},"page":"103-117","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":6,"title":["On the existence of a connected component of a graph"],"prefix":"10.1177","volume":"4","author":[{"given":"Kirill","family":"Gura","sequence":"first","affiliation":[{"name":"Department of Mathematics, Marshall University, 1 John Marshall Drive, Huntington, WV 25755, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffry L.","family":"Hirst","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Appalachian State University, Walker Hall, Boone, NC 28608, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carl","family":"Mummert","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Marshall University, 1 John Marshall Drive, Huntington, WV 25755, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2015,7,1]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310125"},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.12.020"},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1294186663"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1294170993"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/6465"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-012-0150-9"},{"key":"ref007","unstructured":"[7]H.Friedman, Some systems of second order arithmetic and their use, in: Proceedings of the International Congress of Mathematicians (Vancouver, B.C., 1974), Vol. 1, Canad. Math. Congress, Montreal, Que., 1975, pp. 235\u2013242."},{"issue":"2","key":"ref008","doi-asserted-by":"crossref","first-page":"557","DOI":"10.2307\/2272234","volume":"41","author":"Friedman H.","year":"1976","journal-title":"J. Symbolic Logic"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF01269946"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.3233\/COM-2012-005"},{"key":"ref011","unstructured":"[11]S.Le Roux and A.Pauly, Weihrauch degrees of finding equilibria in sequential games, available at: arXiv:1407.5587."},{"key":"ref012","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)72003-2"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200910104"},{"key":"ref014","unstructured":"[14]A.Pauly and W.Fouch\u00e9, How constructive is constructing measures? available at: arXiv:1409.3428."},{"key":"ref015","unstructured":"[15]S.G.Simpson, Subsystems of Second Order Arithmetic, 2nd edn, Perspectives in Logic, Cambridge Univ. Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009."}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-150039","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-150039","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-150039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:45Z","timestamp":1777391985000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-150039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,1]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,7,24]]}},"alternative-id":["10.3233\/COM-150039"],"URL":"https:\/\/doi.org\/10.3233\/com-150039","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,1]]}}}