Graduate Project Paper on Colorful Paths in Vertex Coloring of A Graph
No Thumbnail Available
Date
2012-01-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
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.
Description
Keywords
Graduate Project Paper, Colorful Paths, Vertex Coloring, Graph