  Given a graph, an $L(p,1)$-labeling of the graph is an assignment $f$ from
the vertex set to the set of nonnegative integers such that for any pair of
vertices $(u,v),|f (u) - f (v)| \ge p$ if $u$ and $v$ are adjacent, and $f(u)
\neq f(v)$ if $u$ and $v$ are at distance $2$. The $L(p,1)$-labeling problem is
to minimize the span of $f$ (i.e.,$\max_{u\in V}(f(u)) - \min_{u\in
V}(f(u))+1$). It is known to be NP-hard even for graphs of maximum degree $3$
or graphs with tree-width 2, whereas it is fixed-parameter tractable with
respect to vertex cover number. Since vertex cover number is a kind of the
strongest parameter, there is a large gap between tractability and
intractability from the viewpoint of parameterization. To fill up the gap, in
this paper, we propose new fixed-parameter algorithms for $L(p,1)$-Labeling by
the twin cover number plus the maximum clique size and by the tree-width plus
the maximum degree. These algorithms reduce the gap in terms of several
combinations of parameters.
