Weak Colorings of Computable Hypergraphs
Conner J. Hatton · Scholarship & Creative Works - Digital UNC a service of University Libraries (University of Northern Colorado) · 2018
After introducing the reader to hypergraphs and their colorings, we generalize computable and highly computable graphs to develop the notion of computable and highly computable hypergraphs. If for a graph G we define x(G) as the chromatic number of G and xC(G)to be the computable chromatic number of G, then Bean showed that for every connected computable and highly computable graph G where x(G) = 2, then xC(G) = 2. We show that there exists a 3-uniform, connected hypergraph H such that xH) = 2 and xC(H) = 1. Furthermore, we show that there exists a connected highly computable hypergraph H such that x(H) = 2 and xC(H) = 3. Lastly, we show that for every highly computable hypergraph H where x(H) = k, it follows that xC(H) x 2k.