TV Transmitters

Date: 07/22/97 at 14:09:34
From: kim Parsons
Subject: Graph theory

Television transmitters in a region are to be assigned a channel over 
which to operate. If two transmitters are within 150 kilometers of 
each other, they must be assigned different channels. The chart below 
represents 6 transmitters and their distance from each other.

              N.Y.A    N.Y.B    Harris.   Allen.   Phila.    Balt.
 N.Y.A          0km     20km     280km    100km    160km    315km
 N.Y.B                   0km     260km     80km    140km    305km
 Harrisburg                        0km    175km    165km    145km
 Allentown                                  0km     80km    240km
 Philadelphia                                        0km    155km
 Baltimore                                                    0km

Construct a graph that represents this problem and use it to determine 
the number of channels needed for the region.

Date: 07/28/97 at 12:44:56
From: Doctor Rob
Subject: Re: Graph theory

Make a vertex for each transmitter. For each pair of transmitters with
a distance less than 150km, draw an edge. Channels must be different 
at each end of each edge. All three channels must be different at each
corner of a triangle. All four channels must be different at each
vertex in a complete graph on four vertices, and so on. (This last
rule doesn't apply to this example.

The problem is reduced to coloring the vertices of this graph with a
minimum number of colors.

It looks to me as though three channels will be required for NYA, NYB,
and Allentown. Philadelphia can be the same as NYA. Baltimore and
Harrisburg can be anything but unequal to each other, since they are
connected only to each other and not to the rest.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/