Reverse mathematics and the coloring number of graphs (Q5963197)

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.