Rankings of graphs

A vertex (edge) coloring Φ : V → {1, 2,...,t} (Φ′ : E → {1, 2,..., t}) of a graph G = (V, E) is a vertex (edge) t-ranking if, for any two vertices (edges) of the same color, every path between them contains a vertex (edge) of larger color. The vertex ranking number χ_r(G) (edge ranking number χ′_r(G)) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. It is shown that χ_r(G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize the graphs where the vertex ranking number χ_rand the chromatic number χ coincide on all induced subgraphs, show that χ_r(G) = χ(G) implies χ(G) = ω(G) (largest clique size), and give a formula for χ′_r(K_n).