Rankings of graphs

A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶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 $$\chi '_r \left( G \right)$$ ) 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. Among others 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 those graphs where the vertex ranking number χ _r and the chromatic number χ coincide on all induced subgraphs, show that χ _r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .