Brunel University Research Archive (BURA) >
College of Engineering, Design and Physical Sciences >
Dept of Mathematics >
Dept of Mathematics Research Papers >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/3832

Title: k-L(2, 1)-labelling for planar graphs is NP-complete for k>=4
Authors: Eggemann, N
Havet, F
Noble, S D
Keywords: frequency assignment problem
graph labelling
planar graph
complexity
Publication Date: 2009
Abstract: A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,...,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>=4, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for k<=3. For even k>=8, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any k>=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.
URI: http://bura.brunel.ac.uk/handle/2438/3832
Appears in Collections:Mathematical Science
Dept of Mathematics Research Papers

Files in This Item:

File Description SizeFormat
Fulltext.pdf208.79 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.