Premium
On the chromatic number of disk graphs
Author(s) -
Malesińska Ewa,
Piskorz Steffen,
Weißenfels Gerhard
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199808)32:1<13::aid-net2>3.0.co;2-m
Subject(s) - chromatic scale , combinatorics , chordal graph , unit disk , clique , computer science , indifference graph , unit disk graph , mathematics , clique sum , discrete mathematics , clique number , graph , 1 planar graph , telecommunications , wireless network , wireless
Colorings of disk graphs arise in the study of the frequency‐assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their different generalizations. For all these graphs including the most general class of the double disk (DD) graphs, it is shown that χ( G ) ≤ c · ω( G ) for a constant c . Several coloring algorithms are analyzed for disk graphs, aiming to improve the bounds on χ( G ). We find that their worst‐case performance expressed in the number of used colors is indeed reached in some instances. © 1998 John Wiley & Sons, Inc. Networks 32: 13–22, 1998