Back to Search Start Over

Channel assignment and multicolouring of the induced subgraphs of the triangular lattice

Authors :
Frédéric Havet
Source :
Discrete Mathematics. 233(1-3):219-231
Publication Year :
2001
Publisher :
Elsevier BV, 2001.

Abstract

A basic problem in the design of mobile telephone networks is to assign sets of radio frequency bands (colours) to transmitters (vertices) to avoid interference. Often the transmitters are laid out like vertices of a triangular lattice in the plane. We investigate the corresponding colouring problem of assigning sets of colours of given size k to vertices of the triangular lattice so that the sets of colours assigned to adjacent vertices are disjoint. We prove here that every triangle-free induced subgraph of the triangular lattice is ⌈7k/3⌉-[k]colourable. That means that it is possible to assign to each transmitter of such a network, k bands of a set of ⌈7k/3⌉, so that there is no interference.

Details

ISSN :
0012365X
Volume :
233
Issue :
1-3
Database :
OpenAIRE
Journal :
Discrete Mathematics
Accession number :
edsair.doi.dedup.....5500bb92c8ebb62a252ba4933e9ea191
Full Text :
https://doi.org/10.1016/s0012-365x(00)00241-7