ALCOMFT-TR-03-158

Sotiris Nikoletseas, Vicky Papadopoulou and Paul Spirakis
Radiocoloring Graphs via the Probabilistic Method
Patras. Work packages 2 and 4. December 2003.

Abstract: We employ here the Probabilistic Method, a way of reasoning which shows existence of combinatorial structures and properties to prove refute conjectures.

The radiocoloring problem (RCP) is the problem of assigning frequencies to the transmitters of a network so that transmitters of distance one get frequencies that differ by at least two and any two transmitters of distance one get frequencies that differ by at least one. The objective of an assignment may be to minimize the number of frequencies used (order) or the range of them (span). Here, we study the optimization version of RCP where the objective is to minimize the order. In graph theory terms the problem is modelled by a variation of the vertex graph coloring problem. We investigate upper bounds for the minimum number of colors needed in a radiocoloring assignment of a graph G.

We first provide an upper bound for the minimum number of colors needed to radiocolor a graph G of girth at most 7.

Then, we study whether the minimum order of a radiocoloring assignment is determined by local conditions, i.e. by the minimum order radiocoloring assignment of some small subgraphs of it. We state a related conjecture which is analogous to a theorem of Molloy and Reed for the vertex coloring problem [MR01]. We then investigate whether the conjecture contradicts a Theorem of Molloy and Reed for the vertex coloring when applied on the graph G² obtained by G. The graph G² has the same vertex set as G and there is an edge in G² between any two vertices iff their distance in G is at most 2. We prove that there is no case where the conjecture stated here contradicts the Theorem of Molloy and Reed.

Postscript file: ALCOMFT-TR-03-158.ps.gz (211 kb).