Please use this identifier to cite or link to this item: https://idr.nitk.ac.in/jspui/handle/123456789/17069
Title: Radio k-Coloring and k-Distance Coloring of Graphs
Authors: K, Niranjan P.
Supervisors: Kola, Srinivasa Rao.
Keywords: Department of Mathematical and Computational Sciences;radio k-coloring;Span;radio k-chromatic number;radio coloring;radio number;k-distance coloring;distance coloring;k-distance chromatic number;2-distance coloring;2-distance chromatic number
Issue Date: 2021
Publisher: National Institute of Technology Karnataka, Surathkal
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.
URI: http://idr.nitk.ac.in/jspui/handle/123456789/17069
Appears in Collections:1. Ph.D Theses

Files in This Item:
File Description SizeFormat 
165069 MA16F03 - Niranjan P K.pdf804.46 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.