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 | Size | Format | |
---|---|---|---|---|
Sudipta Ghosh, Mtech Cs. (2019-21)..pdf | 514.01 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.