On the existence of a connected component of a graph

DOI10.3233/COM-150039MaRDI QIDQ3195646zbMATH OpenOpenAlexFDO

Authors Kirill Gura, Jeffry L. Hirst, Carl Mummert

Publication date 20 October 2015

Published in Computability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.4786

zbMATH Keywords

componentconnectedgraphparallelizationpartitionreverse mathematicsWeihrauch reducibility

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35)

Abstract: 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 $mathsf{ACA}_0$ over $mathsf{RCA}_0$. 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 $mathsf{RCA}_0$ or is equivalent to induction for $Sigm{a}_2^0$ formulas, depending on the formulation of the bound on the number of components.

Recommendations

• Connected components of graphs and reverse mathematics
• scientific article; zbMATH DE number 1187507
• Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\)
• Reverse Mathematics and Recursive Graph Theory
• Reverse mathematics and infinite traceable graphs

Cites work

• Closed choice and a uniform low basis theorem
• Connected components of graphs and reverse mathematics
• Effective Borel measurability and reducibility of functions
• Effective Choice and Boundedness Principles in Computable Analysis
• On the (semi)lattices induced by continuous reducibilities
• On the strength of the finite intersection principle
• Weihrauch degrees, omniscience principles and weak computability

Cited in

(6)

• Connected components of graphs and reverse mathematics
• The uniform content of partial and linear orders
• Reverse mathematics of matroids
• Weihrauch Complexity in Computable Analysis
• An inside/outside Ramsey theorem and recursion theory
• Primitive recursive reverse mathematics

This page was built for publication: On the existence of a connected component of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3195646)