Coloring rings
Frédéric Maffray, Irena Penev, Kristina Vušković · Journal of Graph Theory · 2020
Abstract A ring is a graph whose vertex set can be partitioned into nonempty sets, , such that for all , the set can be ordered as so that . A hyperhole is a ring such that for all , is complete to . In this paper, we prove that the chromatic number of a ring is equal to the maximum chromatic number of a hyperhole in . 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 ‐bounding function for this larger class of graphs, and we also verify Hadwiger's conjecture for it.