Clique Number vs. Chromatic Number in Wireless Interference Graphs: Simulation Results

Interference due to transmissions by adjacent nodes in a multi-hop wireless network can be modeled using a unit disc graph (UDG). We investigate the reliability associated with using the clique number instead of the chromatic number of the UDG while computing the interference. In our extensive simulations with UDGs of random networks, we observed that the clique number and the chromatic number values were typically very close to one another and the maximum deviation was much less than the theoretical bounds. This implies very high reliability in the proposed approximation.