Back to Search
Start Over
Channel assignment and multicolouring of the induced subgraphs of the triangular lattice
- 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.
- Subjects :
- Discrete mathematics
Plane (geometry)
Transmitter
Induced subgraph
Disjoint sets
Astrophysics::Cosmology and Extragalactic Astrophysics
Interference (wave propagation)
Theoretical Computer Science
Combinatorics
Set (abstract data type)
Discrete Mathematics and Combinatorics
Hexagonal lattice
Channel (broadcasting)
Mathematics
Computer Science::Information Theory
Subjects
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