A Coloring Problem on Chordal Rings

A graph \(G\) having \(7\) vertices is called a chordal ring if its vertices can be arranged in a Hamiltonian cycle \(0, 1, 2, \ldots, n-1\) and there is a proper divisor \(d\) of \(n\) such that for all vertices \(i\) and \(j\), \(i\) is adjacent to \(j\) in \(G\) if and only if \(i+d\) is adjacent to \(j+d\) (addition modulo \(n\)). We consider here the efficacy of coloring the vertices of such a graph by the greedy algorithm applied to the vertices in the order of their appearance on the cycle. For any positive integer \(n\), let \(\Sigma_n\) denote the set of all permutations of the set \(\{1, 2, \ldots, n\}\) together with the adjacency relation \(\sim\) defined as follows: for \(\sigma\) and \(\tau\) in \(\Sigma_n\), \(\sigma \sim \tau\) if and only if there is an integer \(i\) such that \(\sigma-i = \tau-i\). (Here \(\sigma-i\) denotes the permutation of length \(n-1\) obtained by deleting \(i\) from \(\sigma\).) In this paper, we study some of the properties of the graph \((\Sigma_n, \sim)\). Two of the results obtained are the following:
(i) \((\Sigma_n, \sim)\) is a chordal ring for every positive integer \(n\);
(ii) the chromatic number of \(\Sigma_5\) is \(5\) but the greedy algorithm colors \(\Sigma_5\) in \(9\) colors.