Coloring rings

Abstract

A ring is a graph $R$ whose vertex set can be partitioned into $k\ge 4$ nonempty sets, $X_1,\dots ,X_k$, such that for all $i\in \{1,\dots ,k\}$, the set $X_i$ can be ordered as $X_i=\{u_i^1,\dots ,u_i^{|X_i|}\}$ so that $X_i\subseteq N_R[u_i^{|X_i|}]\subseteq \cdots \subseteq N_R[u_i^1]=X_{i-1}\cup X_i\cup X_{i+1}$. A hyperhole is a ring $R$ such that for all $i\in \{1,\dots ,k\}$, $X_i$ is complete to $X_{i-1}\cup X_{i+1}$. 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, Penev, and Vušković in [Journal of 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.