Some properties of L(2,1)-coloring as related to the channel assignment problem

The channel assignment problem is the problem of efficiently assigning frequencies to radio transmitters located at various places such that communications do not interfere. In 1988, F. S. Roberts [40] proposed (in a private communication with Griggs) the problem of efficiently assigning radio channels to transmitters at several locations, using non-negative integers to represent channels, so that close locations receive different integers, and channels of very close locations are at least 2 apart. This evolved into the study of L(2,1)-coloring of a graph first studied by Griggs and Yeh [25].; In this thesis, we investigate sum colorings and the sum coloring number of certain classes of graphs. Theorem 6 of page 25 and Theorem 7 of page 29 are the main results' in this section. In these theorems, we prove that if Pn is a path on n vertices, then Sigma( Pn) = 2(n - 1) for all positive integers n and if Cn is a cycle on n ≥ vertices, then Sigma(Cn) = 2n respectively. Exact values for the sum coloring numbers of stars and complete graphs are given. Complete graphs are characterized in terms of their sum coloring number. We also conjecture an upper bound for the sum coloring number of an arbitrary graph G with span lambda( G). Holes in L(2,1)-colorings on certain classes of graphs are studied with an emphasis on the maximum number of holes in an L(2,1)-coloring of a graph. The main results in this section are Theorem 10 of page 39, Theorem 11 of page 41 (giving exact values for the maximum number of holes in a span coloring of a path Pn on n vertices and a cycle Cn on n vertices) and Theorem 15 of page 54 (proving that all diameter-2 graphs are good graphs). Exact values and bounds for the maximum number of holes in span colorings of other classes of graphs are given. We also investigate span colorings that have the property of being a sum coloring and having the maximum number of holes in a graph G. We shall call such colorings grand L(2, 1)-colorings.