On Interference Graphs

The study of interference graphs assumes significance in the context of the study of Frequency assignment problem. By an interference graph we mean the graph whose vertices represent a transmitter and the edges denote the interference constraint between two adjacent transmitters. In this paper we probe the relationship between 2-coloring and radio labeling and the effect of its computational aspect to certain restricted class of graphs. We also indicate some possible directions for further research.