Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/3832
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Eggemann, N | - |
dc.contributor.author | Havet, F | - |
dc.contributor.author | Noble, S D | - |
dc.coverage.spatial | 16 | - |
dc.date.accessioned | 2009-11-11T16:35:34Z | - |
dc.date.available | 2009-11-11T16:35:34Z | - |
dc.date.issued | 2009 | - |
dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/3832 | - |
dc.description.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. | en |
dc.language.iso | en | en |
dc.subject | frequency assignment problem | en |
dc.subject | graph labelling | en |
dc.subject | planar graph | en |
dc.subject | complexity | en |
dc.title | k-L(2, 1)-labelling for planar graphs is NP-complete for k>=4 | en |
dc.type | Preprint | en |
Appears in Collections: | Dept of Mathematics Research Papers Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Fulltext.pdf | 208.79 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.