RANKINGS OF GRAPHS

A vertex (edge) coloring phi : V --> {1, 2, ..., t} (phi' : 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 c ontains a vertex (edge) of larger color. The vertex ranking number chi (r)(G) (edge ranking number chi(r)' (G)) is the smallest value of t su ch that G has a vertex (edge) t-ranking. In this paper we study the al gorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. It is shown that chi(r)(G) can be computed in polynomial time when res tricted to graphs with treewidth at most k for any fixed k. We charact erize the graphs where the vertex ranking number chi(r) and the chroma tic number chi coincide on all induced subgraphs, show that chi(r)(G) = chi(G) implies chi(G) = omega(G) (largest clique size), and give a f ormula for chi(r)' (K-n).