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. | Yugoslav Journal of Operations Research 13 (2003), Number 2, 207-215 GRAPH RADIOCOLORING CONCEPTS R. KALFAKAKOU, G. NIKOLAKOPOULOU, E. SAVVIDOU, M. TSOUROS Aristotle University of Thessaloniki, Faculty of Engineering Thessaloniki, Greece 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. Keywords: Graph, radio coloring, algorithm, channel assignment. 1. INTRODUCTION Graph colouring is one of the oldest concepts in the theory of graphs, it has preoccupied a large number of people as a distraction puzzle during the 19th century and later in the framework of scientific research, since this conception exhibits a significant interest from a theoretical and practical point of view. Many applications are modelised and investigated with the use of graph coloring. Because of the technology evolution, new problems arised that can be expressed effectively by handling invariants that are generalizations of graph coloring, see [1]. Here we present the notion of radio coloring which is a generalization of Graph coloring. The term radio coloring is due to [2]. For reason of self-reliance and from the fact that graph .
