$k$-$L(2,1)$-Labelling for Planar Graphs is NP-Complete for $k\geq 4$ - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

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

Nicole Eggemann
• Fonction : Auteur
Frédéric Havet
Steven Noble
• Fonction : Auteur

#### Résumé

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. % planar graphs for $k\geq 8$. 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.

#### Domaines

Informatique [cs] Mathématique discrète [cs.DM]

### Dates et versions

inria-00360505 , version 1 (11-02-2009)

### Identifiants

• HAL Id : inria-00360505 , version 1

### Citer

Nicole Eggemann, Frédéric Havet, Steven Noble. $k$-$L(2,1)$-Labelling for Planar Graphs is NP-Complete for $k\geq 4$. [Research Report] RR-6840, INRIA. 2009. ⟨inria-00360505⟩

### Exporter

BibTeX TEI Dublin Core DC Terms EndNote Datacite

### Collections

276 Consultations
168 Téléchargements