Upper bounds for the span in triangular lattice graphs: application to frequency planning for cellular network

We study a problem coming from the design of wireless cellular radiocommunication network. Frequency planning constraints are modelled in terms of graph theory. For each planning function $f$ let us call $sp(f)$ - or the {\em span} of the frequency planning $f$ - the difference between the largest and the smallest frequency used. Let the {\em Order} of the graph be $Or(G)=sp(G)+1$ and the {\em maximal local order} of the graph the maximum order of a clique of $G$, i.e. $Mlo(G) = \max_{X \ \mbox{clique of}\ G} sp(X)$. We show: $Mlo(G) \leq sp(G) \leq 8\lceil\frac{Mlo(G)}{6}\rceil$.Ce rapport explore un problème issue de l'allocation de fréquence dans les réseaux de radiocommunication cellulaire. Le problème de planification est décrit à l'aide de la théorie des graphes. Pour une fonction donnée $f$ de plannification, on appelle le {\em span} de $f$ - ou $sp(f)$ - la différence entre la plus grande fréquence employée et la plus petite. Nous définissons aussi l'{\em ordre } du graphe comme étant $Or(G)=sp(G)+1$ et l'{\em ordre local maximum} $Mlo(G)$ comme étant l'ordre maximum d'une clique de $G$, c'est-à-dire $Mlo(G) = \max_{X \ \mbox{clique of}\ G} sp(X)$. Nous montrons le résultat suivant : $Mlo(G) \leq sp(G) \leq 8\lceil\frac{Mlo(G)}{6}\rceil$