Reverse Mathematics and Recursive Graph Theory

DOI10.1002/MALQ.19980440405MaRDI QIDQ4224080zbMATH OpenOpenAlexFDO

Authors Jeffry L. Hirst, William Gasarch

Publication date 19 August 1999

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

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

zbMATH Keywords

Eulerian pathsgraph theoryHamiltonian pathsreverse mathematicssecond-order arithmetic

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45) Second- and higher-order arithmetic and fragments (03F35) Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45)

Abstract: We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.

Recommendations

• Graph Coloring and Reverse Mathematics
• Reverse mathematics and colorings of hypergraphs
• Reverse mathematics and the coloring number of graphs
• scientific article; zbMATH DE number 1187507

Cites work

• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• scientific article; zbMATH DE number 1303203 (Why is no real title available?)
• scientific article; zbMATH DE number 728180 (Why is no real title available?)
• Recursive Colorings of Graphs

Cited in

(15)

• Reverse binary graphs
• Reverse mathematics and rank functions for directed graphs
• Connected components of graphs and reverse mathematics
• Reverse mathematics and colorings of hypergraphs
• Schmerl decompositions in first order arithmetic
• Domatic partitions of computable graphs
• Comparing the strength of diagonally nonrecursive functions in the absence of _2⁰ induction
• Reverse mathematics and infinite traceable graphs
• On the existence of a connected component of a graph
• scientific article; zbMATH DE number 4148082 (Why is no real title available?)
• scientific article; zbMATH DE number 1187507 (Why is no real title available?)
• Graph Coloring and Reverse Mathematics
• An inside/outside Ramsey theorem and recursion theory
• scientific article; zbMATH DE number 2236643 (Why is no real title available?)
• Reverse mathematics and the coloring number of graphs

This page was built for publication: Reverse Mathematics and Recursive Graph Theory

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