Graduate Project Paper On Colorful Paths In Vertex Coloring Of A Graph

This project paper is mainly focused on connected simple graph G and onrnthe existence of a v-colorful path and rainbow path for any _ _ __ _(thernset of all vertices of a graph G) of a given length, and algorithms to findrnthose colorings.rnThe first section contains the short summary of the paper and definitionrnand application of tree search algorithms, as well as the comparisonsrnbetween the two and the historical background of coloring.rnThe second section contains the basic definitions of graphs. We definerncolorings-vertex, edge and total colorings illustrate them with examples. itrnalso focuses on the definition of chromatic number, the bounds forrnchromatic number in the first section and then defines about walk, trailrnand path as well as definitions of colorful and rainbow paths. Finally wernintroduce two tree traversal algorithms, of which one is to be used in thernalgorithms.rnIn section three, we are going to show the basic results of this paper,rnwhich is, the algorithm needed to color different types of simplernconnected graphs with different set of colors to show the existence ofrnv-colorful paths and v-rainbow path of a given length for all v_ __ _.rnSome important theorems and lemmas are proved; Examples are alsornprovided to illustrate each case.

Get Full Work

Report copyright infringement or plagiarism