On the Radiocoloring Problem

(Extended Abstract)

T. Calamoneri and R. Petreschi

Abstract

In this paper a survey on the Radiocoloring Problem is presented. The Radiocoloring Problem (RCP) consists of an assignment of colors from the integer set $(0..\lambda)$ to the vertices of a graph, such that vertices at a distance of at most two get different colors and adjacent vertices get colors which are at least two apart. The aim is to minimize $\lambda$. The RCP arose in the field of wireless radio networks, and it concerns the problem of frequency assignment. Since its formal definition, the RCP has been widely studied due both to its intrinsic theoretical interest and to the growth of wireless networks.

PS Files

Conference Version