Résumé
The L(p, q) -EDGE-LABELLING problem is the edge variant of the well-known L(p, q)-LABELLING problem. It is equivalent to the L(p, q)-LABELLING problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p, q) -EDGE-LABELLING was only partially classified in the literature. We complete this study for all p, q= 0 by showing that whenever (p, q) ? (0, 0), the L(p, q) -EDGE-LABELLING problem is NP-complete. We do this by proving that for all p, q > 0 except p = q = 0, there is an integer k so that L(p, q)- EDGE- k LABELLING is NP-complete.