In this paper, we introduce two new variations on the computable chromatic number: the computable list chromatic number and the computable coloring number. We show that, just as with the non-computable versions, the computable chromatic number is always less than or equal to the computable list chromatic number, which is less than or equal to the computable coloring number.We investigate the potential differences between the computable and non-computable chromatic, list chromatic, and coloring numbers on computable graphs. One notable example is a computable graph for which the coloring number is 2, but the computable chromatic number is infinite.
| Identifer | oai:union.ndltd.org:siu.edu/oai:opensiuc.lib.siu.edu:theses-4307 |
| Date | 01 August 2024 |
| Creators | Thomason, Seth Campbell |
| Publisher | OpenSIUC |
| Source Sets | Southern Illinois University Carbondale |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Theses |
Page generated in 0.0024 seconds