Graduate Project Paper on Colorful Paths in Vertex Coloring of A Graph

No Thumbnail Available



Journal Title

Journal ISSN

Volume Title


Addis Ababa University


This project paper is mainly focused on connected simple graph G and on the existence of a v-colorful path and rainbow path for any _ _ __ _(the set of all vertices of a graph G) of a given length, and algorithms to find those colorings. The first section contains the short summary of the paper and definition and application of tree search algorithms, as well as the comparisons between the two and the historical background of coloring. The second section contains the basic definitions of graphs. We define colorings-vertex, edge and total colorings illustrate them with examples. it also focuses on the definition of chromatic number, the bounds for chromatic number in the first section and then defines about walk, trail and path as well as definitions of colorful and rainbow paths. Finally we introduce two tree traversal algorithms, of which one is to be used in the algorithms. In section three, we are going to show the basic results of this paper, which is, the algorithm needed to color different types of simple connected graphs with different set of colors to show the existence of v-colorful paths and v-rainbow path of a given length for all v_ __ _. Some important theorems and lemmas are proved; Examples are also provided to illustrate each case.



Graduate Project Paper, Colorful Paths, Vertex Coloring, Graph