First Advisor
Levin, Oscar
Degree Name
Bachelor of Science
Document Type
Thesis
Date Created
5-2018
Department
College of Natural and Health Sciences, Mathematical Sciences, Mathematical Sciences Student Work
Abstract
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.
Extent
24 pages
Local Identifiers
Hatton_HonorsThesis2018
Rights Statement
Copyright is held by the author.
Recommended Citation
Hatton, Conner, "Weak Colorings of Computable Hypergraphs" (2018). Undergraduate Honors Theses. 12.
https://digscholarship.unco.edu/honors/12