Radio k-Coloring and k-Distance Coloring of Graphs

Abstract

The frequency assignment problem is the problem of assigning frequencies to transmitters in an optimal way and with no interference. Interference can occur if transmitters located sufficiently close to each other receive close frequencies. The frequency assignment problem motivates many graph coloring problems. Motivated by this, we study radio k-coloring and k-distance coloring of graphs. In this thesis, we study radio k-coloring of paths, trees, Cartesian product of graphs and corona of graphs; k-distance coloring of trees, cycles and cactus graphs. A radio k-coloring of a simple connected graph G is an assignment f of positive integers (colors) to the vertices of G such that for every pair of distinct vertices u and v in G, j f (u)􀀀 f (v)j is at least 1+k􀀀d(u;v). The span of f , rck( f ), is the maximum color assigned by f . The radio k-chromatic number rck(G) is minfrck( f ) : f is a radio k-coloring of Gg. If d is the diameter of G, then a radio d-coloring and the radio d-chromatic number are referred as a radio coloring and the radio number rn(G) of G. Since finding the radio k-chromatic number is highly nontrivial, it is known for very few graphs and that too for some particular values of k only. For k 6, we determine the radio k-chromatic number of path Pn for 2n+1 7 k n􀀀4 if k is odd and for 2n􀀀4 5 k n􀀀5 if k is even. For some classes of trees, we obtain an upper bound for the radio k-chromatic number when k is at least the diameter of the tree. Also, for the same, we give a lower bound which matches with the upper bound when k and the diameter of the tree are of the same parity. Further, we determine the radio d-chromatic number of larger trees constructed from the trees of diameter d in some subclasses of the above classes. We determine the radio number for some classes of the Cartesian product of complete graphs and cycles. We obtain a best possible upper bound for the radio k-chromatic number of corona G H of arbitrary graphs G and H. Also, we obtain a lower bound and an improved upper bound for the radio number of Qn H and P2p+1 H. A k-distance coloring of a simple connected graph G is an assignment f of positive integers to the vertices of G such that no two vertices at distance less than or equal to k receive the same color. If a is the maximum color assigned by f , then f is referred as a k-distance a-coloring. The k-distance chromatic number ck(G) is the minimum a such that G has a k-distance a-coloring. We determine the k-distance chromatic number for trees and cycles. Also, we determine the 2-distance chromatic number of cactus graphs.