Abstrakt
A ring is a graph whose vertex set can be partitioned into k >= 4 nonempty sets, X_1, ..., X_k with a special structure. In this paper, we prove that the chromatic number of a ring R is equal to the maximum chromatic number of a hyperhole in R.
Using this result, we give a polynomial-time coloring algorithm for rings. Rings formed one of the basic classes in a decomposition theorem for a class of graphs studied by Boncompagni et al [J.
Graph Theory 91 (2019), 192-246.]. Using our coloring algorithm for rings, we show that graphs in this larger class can also be colored in polynomial time.
Furthermore, we find the optimal chi-bounding function for this larger class of graphs, and we also verify Hadwiger's conjecture for it.