×

On a generalized family of colorings. (English) Zbl 0716.05018

By a graph \(G=(V,E)\) we mean the vertex set V corresponded to the cells (in telecommunication technology) and the edges in E connected neighbouring cells with the metric induced by the shortest path between vertices. The call chromatic number \(C^ f_ R(G)\) of G consists in assigning f(x) colours (frequencies) to each vertex x in V with the constraint that within any ball (x,R) of radius \(R>0\), all colours are different. There are given bounds and colouring algorithms of \(C^ f_ R(G)\) for trees, n-cycles, hypercubes, square and triangular lattices respectively. Some generalizations, a connection to Heawood’s map colour theorem and open problems are considered too.
Reviewer: J.Fiamčík

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baldi, P.: (1) On a Generalized Family of Colorings (2) Some Contributions to the Theory of Neural Networks (3) Embeddings of Ultrametric Spaces. Ph.D. Thesis, California Institute of Technology, May 1986
[2] Baldi, P., Posner, E.C.: Graph Coloring Bounds for Cellular Radio. International Journal of Computers and Mathematics with Applications.19, no. 10, 91–97 (1990) · Zbl 0687.05020 · doi:10.1016/0898-1221(90)90361-M
[3] Hoffman, A.J., Singleton, R.R.: On Moore Graphs with Diameter 2 and 3.IBM Journal Nov. 1960 · Zbl 0096.38102
[4] Posner, E.C.: Frequency Assignment in Cellular Radio. In: Open Problems in Communication and Computation (T.M. Cover, B. Gopinath eds.) pp. 100–101. New York: Springer-Verlag 1987
[5] Young, W.R.: Advanced Mobile Phone Service, Introduction Background and Objectives. Bell System Technical Journal59, 1–14 (1973)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.