L(2,1)-labelling of graphs with few P4's

Given a simple graph G, an L(2,1)-labelling (or λ-labelling) of G is a function c:V(G)→N such that |c(x)−c(y)|≥2, if x and y are neighbors and |c(x)−c(y)|≥1 if x and y have a common neighbor. The span of a labelling is the difference of the smallest and largest labels used. An L(2,1)-span of a graph G, denoted by λ(G), is a minimum span over all L(2,1)-labellings of G. The problem of determining if λ(G)≤k is NP-Complete for any k≥4. In this paper, we obtain a linear time algorithm to compute λ(G) for any (q,q−4)-graph with q fixed. Another important topic regarding the λ-labelling is to bound the λ-chromatic number of a graph by some function of it. Griggs and Yeh conjectured that λ(G)≤Δ2 for any graph G with maximum degree Δ≥2. They also proved that the greedy algorithm for the problem uses at most Δ2+Δ. Furthermore we prove that the Griggs-Yeh conjecture is true for P4-sparse graphs, P4-laden graphs and all (q,q−4)-graphs with at least 3q/2 vertices.