کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420272 | 683915 | 2010 | 12 صفحه PDF | دانلود رایگان |
A mapping from the vertex set of a graph G=(V,E)G=(V,E) into an interval of integers {0,…,k}{0,…,k} is an L(2,1)L(2,1)-labelling of GG of span kk if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices at distance 2 are mapped onto distinct integers. It is known that, for any fixed k≥4k≥4, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for k≤3k≤3. For even k≥8k≥8, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any k≥4k≥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.
Journal: Discrete Applied Mathematics - Volume 158, Issue 16, 28 August 2010, Pages 1777–1788