Skip to Main content Skip to Navigation
New interface
Journal articles

k-L(2,1)-Labelling for Planar Graphs is NP-Complete for $k\geq 4$.

Nicole Eggemann 1 Frédéric Havet 2 Steven Noble 1 
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $\{0, \dots ,k\}$ is an $L(2,1)$-labelling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbour are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for $k\leq 3$. For even $k\geq 8$, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any $k \ge 4$ by reduction from Planar Cubic Two-Colourable Perfect Matching. Schaefer stated without proof that Planar Cubic Two-Colourable Perfect Matching is NP-complete. In this paper we give a proof of this.
Document type :
Journal articles
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Sunday, October 23, 2016 - 4:30:53 PM
Last modification on : Thursday, August 4, 2022 - 4:52:44 PM


Files produced by the author(s)


  • HAL Id : inria-00534520, version 1



Nicole Eggemann, Frédéric Havet, Steven Noble. k-L(2,1)-Labelling for Planar Graphs is NP-Complete for $k\geq 4$.. Discrete Applied Mathematics, 2010, 158 (16), pp.1777-1788. ⟨inria-00534520⟩



Record views


Files downloads