The Complexity of List Ranking of Trees

Abstract

A vertex $k$-ranking of a graph $G$ is a function $c:V(G)\to \{1,\dots ,k\}$ such that if $c(u)=c(v)$, $u,v\in 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)\in L(v)$ for each $v\in V(G)$, then $c$ is called an $L$-list $k$-ranking, where $\mathcal{L}=\{L(v):v\in 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) $\mathcal{L}$-list ranking is polynomially solvable for paths and trees with a bounded number of non-leaves, which includes trees with diameter less than $4$.