Graph radio coloring concepts

Abstract

The evolution of the telecommunication technology, such as mobile telecommunication equipment, radio, television, teleconferencing, etc necessitated the existence of numerously broadcast channels. However the corresponding frequencies may interfere for reason of distance, geographical or atmospherical structure or for a variety of other factors. In the present paper we give the definition of the graph radio coloring concept which is a graph coloring generalization. We also introduce radio coloring invariants which are of a great practical importance to problems regarding the allocation of diverse frequencies in order to avoid interference occurrences between channel transmissions. A heuristic algorithm that finds approximate values of the radio chromatic number and radio chromatic cost of a given graph is developed and the result of a computational experiment of the proposed algorithm is given. .