Please use this identifier to cite or link to this item: http://hdl.handle.net/10263/7314
Title: Rainbow Edge Coloring
Authors: Ghosh, Sudipta
Keywords: Rainbow coloring
Edge Rainbow Coloring
Graph coloring
Squares of Trees
Issue Date: Jul-2021
Publisher: Indian Statistical Institute, Kolkata.
Citation: 30p.
Series/Report no.: Dissertation;CS1902
Abstract: Graph coloring is a well known problem with wide-ranging applications. The vertex and edge coloring problems have been studied in various models of computation. Rainbow coloring is a type of edge coloring that also acts as a connectivity measure for graphs. It was first introduced by Chartrand et al. in 2008.In 2011 Chakrobarty et al. proved that, it NP-Hard to compute rainbow connection number of a graph. In this thesis first we have define some notation for graph and rainbow coloring. Then we do a literature overview of the results about rainbow coloring. In the final part we have proved that, if G is a square of tree, then rc(G) 2 {diam(G),diam(G) + 1},and the corresponding optimal rainbow coloring can be found in the time that is linear in the size of G.
Description: Dissertation under the supervision of Dr. Sourav Chakraborty
URI: http://hdl.handle.net/10263/7314
Appears in Collections:Dissertations - M Tech (CS)

Files in This Item:
File Description SizeFormat 
Sudipta Ghosh, Mtech Cs. (2019-21)..pdf514.01 kBAdobe PDFView/Open


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