✦ LIBER ✦

Graph coloring bounds for cellular radio

✍ Scribed by Pierre Baldi; Edward C. Posner

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 321 KB
Volume: 19
Category: Article
ISSN: 0898-1221
DOI: 10.1016/0898-1221(90)90361-m

No coin nor oath required. For personal study only.

✦ Synopsis

A graph coloring problem usdul in deciding whether a set of call requests in cellular radio is compatible with frequency use constraints is introduced. Lower and upper bounds are obtained for the hexagonal cell case typical of raany urban cellular systems. These bounds are on the number of frequencies needed to satisfy demand when there is an upper bound on the demand with small subsets. For example, if we have 308 frequency channels available, as for American cellular systems, then this is enough to satisfy any set of call requests when every "superhex" of 7 hexagons, 6 around 1, has at most 154 call" requests. But 308 frequencies are definitely not enough if we permit some superhexes to have 206 or more call requests.

📜 SIMILAR VOLUMES

Lower bounds for on-line graph coloring

✍ Magnus M. Halldórsson; Mario Szegedy 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 771 KB

Bounded vertex colorings of graphs

✍ Pierre Hansen; Alain Hertz; Julio Kuplinsky 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 503 KB

Bounded color functions on graphs

✍ D. W. Matula 📂 Article 📅 1972 🏛 John Wiley and Sons 🌐 English ⚖ 753 KB

An edge coloring problem for graph produ

An edge coloring problem for graph products

✍ Faudree, R. J.; Gy�rf�s, Andr�as; Schelp, R. H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 315 KB 👁 1 views

The edges of the Cartesian product of graphs G x H a r e to be colored with the condition that all rectangles, i.e., K2 x K2 subgraphs, must be colored with four distinct colors. The minimum number of colors in such colorings is determined for all pairs of graphs except when G is 5-chromatic and H

Polychromatic colorings of bounded degre

Polychromatic colorings of bounded degree plane graphs

✍ Elad Horev; Roi Krakovski 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 289 KB

## Abstract A __polychromatic k__‐__coloring__ of a plane graph __G__ is an assignment of __k__ colors to the vertices of __G__ such that every face of __G__ has __all k__ colors on its boundary. For a given plane graph __G__, one seeks the __maximum__ number __k__ such that __G__ admits a polychro

Coloring Graphs without Short Non-boundi

Coloring Graphs without Short Non-bounding Cycles

✍ S. Fisk; B. Mohar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 357 KB

It is shown that there is a constant \(c\) such that if \(G\) is a graph embedded in a surface of genus \(g\) (either orientable or non-orientable) and the length of a shortest non-bounding cycle of \(G\) is at least \(c \log (g+1)\), then \(G\) is six-colorable. A similar result holds for three- an