ON THE CHROMATIC NUMBER OF DISK GRAPHS

Colorings of disk graphs arise in the study of the frequency-assignmen t problem in broadcast networks. Motivated by the observations that th e chromatic number of graphs modeling real networks hardly exceeds the ir clique number, we examine the related properties of the unit disk ( UD) graphs and their different generalizations. For all these graphs i ncluding the most general class of the double disk (DD) graphs, it is shown that chi(G) less than or equal to c.omega(G) for a constant c, S everal coloring algorithms are analyzed for disk graphs, aiming to imp rove the bounds on chi(G), We find that their worst-case performance e xpressed in the number of used colors is indeed reached in some instan ces, (C) 1998 John Wiley & Sons, Inc. Networks 32: 13-22, 1998.