k-L(2,1)-Labelling for Planar Graphs is NP-Complete for k >= 4

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

16 pages, includes figures generated using PSTricks. To appear in Discrete Applied Mathematics. Some very minor corrections in

Scientific paper

10.1016/j.dam.2010.06.016

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

k-L(2,1)-Labelling for Planar Graphs is NP-Complete for k >= 4 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with k-L(2,1)-Labelling for Planar Graphs is NP-Complete for k >= 4, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and k-L(2,1)-Labelling for Planar Graphs is NP-Complete for k >= 4 will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-565395

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.