Maximizing the number of edges in optimal \(k\)-rankings (Q896093)

A \(k\)-ranking of a graph \(G\) is an assignment of the colors \(\{1, \ldots, k\}\) to the vertices of \(G\) such that whenever \(v\) and \(w\) receive the same color, every path joining \(v\) and \(w\) contains a vertex with a larger color. In particular, every \(k\)-ranking of \(G\) is a proper \(k\)-coloring of \(G\). The \textit{rank number} of \(G\) is the smallest integer \(k\) such that \(G\) has a \(k\)-ranking; we write \(\chi_r(G)\) for the rank number of \(G\). The rank number is monotone when: if \(H \subset G\), then \(\chi_r(H) \leq \chi_r(G)\). The paper under consideration studies the following problem: given a graph \(G\), how many edges can be added to \(G\) without increasing its rank number? Given a graph \(G\) and a ranking \(f\), say that a possible edge \(e \notin E(G)\) is admissible for \(f\) if \(f\) is still a ranking of \(G+e\). (This definition of admissibility differs from the definition given in the paper, which is that \(e\) is admissible if \(\chi_r(G+e) = \chi_r(G)\), but appears to be the definition that is required for the correctness of some theorems in the paper, in particular Theorem 8. I have confirmed with the corresponding author that this is the intended definition.) The authors consider several graph classes for which the optimal ranking \(f\) is essentially unique, and show that for each class of graph, we may add all the admissible edges simultaneously and retain the property that \(f\) is a ranking. Thus, for these graph classes, the authors determine the exact number of edges that may be added without increasing the ranking number, by counting the size of the set of admissible edges and giving an algorithm to construct this set.