The Complexity of List Ranking of Trees
Dariusz Dereniowski · 2008
Abstract: A vertex k-ranking of a graph G is a function c: V (G) → {1,...,k} such that if c(u) = c(v),u,v ∈ V (G) then each path connecting vertices u and v contains a vertex w with c(w)> c(u). If each vertex v has a list of integers L(v) and for a vertex ranking c it holds c(v) ∈ L(v) for each v ∈ V (G) then c is called L-list k-ranking, where L = {L(v) : v ∈ V (G)}. In this paper we investigate both vertex and edge (vertex ranking of a line graph) list ranking problems. We prove that both problems are NP-complete for several classes of acyclic graphs, like full binary trees, trees with diameter at most 4 and comets. The problem of finding vertex (edge) L-list ranking is polynomially solvable for paths and trees with bounded number of nonleaves, which includes trees with diameter less than 4. 1