k-L2,1-Labelling for Planar Graphs is NP-Complete for k >= 4 - Mathematics > CombinatoricsReport as inadecuate




k-L2,1-Labelling for Planar Graphs is NP-Complete for k >= 4 - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: A mapping from the vertex set of a graph G = V,E into an interval ofintegers {0,

.,k} is an L2,1-labelling of G of span k if any two adjacentvertices are mapped onto integers that are at least 2 apart, and every twovertices with a common neighbour are mapped onto distinct integers. It is knownthat for any fixed k >= 4, deciding the existence of such a labelling is anNP-complete problem while it is polynomial for k <= 3. For even k >= 8, itremains NP-complete when restricted to planar graphs. In this paper, we showthat it remains NP-complete for any k >= 4 by reduction from Planar CubicTwo-Colourable Perfect Matching. Schaefer stated without proof that PlanarCubic Two-Colourable Perfect Matching is NP-complete. In this paper we give aproof of this.



Author: Nicole Eggemann, Frédéric Havet, Steven D. Noble

Source: https://arxiv.org/







Related documents