2008/10/06 by Toru Hasunuma, Toshimasa Ishii, Hasunuma, Toru +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.0810.0906
openalex publication_date 2008/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)-f(y)|≥ 2 if x and y are adjacent and |f(x)-f(y)|≥ 1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an assignment f:V(G)→\0,..., k\, and the L(2,1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of a very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been \mO(Δ4.5 n) for more than a decade, however, an \mO(n1.75)-time algorithm has been proposed recently, which substantially improved the previous one, where Δ is the maximum degree of T and n=|V(T)|. In this paper, we finally establish a linear time algorithm for L(2,1)-labeling of trees.