Browsing by Author "Bekele, Ayele"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
Item Graduate Project Paper on Colorful Paths in Vertex Coloring of A Graph(Addis Ababa University, 2012-01-01) Bekele, Ayele; Tsegaye, Yirgalem (PhD)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.