Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM9805March 1998 
J. van den Heuvel
Abstract
Given a set V of points in the plane, a sequence d_{0},d_{1}, . . . ,d_{k} of nonnegative numbers and an integert n, we are interested in the problem to assign integers from {0, . . . ,n1} to the points in V such that if x, y in V are two points with euclidean distance less than d_{i}, then the difference between the labels of x and y is not equal to i. This question is inspired by problems occurring in the design of radio networks, where radio channels need to be assigned to transmitters in such a way that interference is minimised. In this paper we consider the case that the set of points are the points of a 2dimensional lattice. Recent results by McDiarmid and Reed show that if only one constraint d_{0} is given, good labellings can be obtained by using socalled strict tilings. We extend these results to the case that higher level constraints d_{0},d_{1}, . . . ,d_{k} occur. In particular we study conditions that guarantee that a strict tiling, satisfying only the one constraint d_{0}, can be transformed to a strict tiling satisfying the higher order constraints as well. Special attention is devoted to the case that the points are the points of a triangular lattice.
A compressed (gzip) PostScript file (112 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you like a free hard copy of this report, please send the number of this report, LSECDAM9805, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)171955 7732. Fax: +44(0)171955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last changed: Wed 9 Feb 2005
For comments go to:
http://www.maths.lse.ac.uk/webmaster.html