PLANAR GRAPHS AND COLORING
Loading...
Date
2010-05
Authors
MANOGARAN, LAVANEESVARI
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The key aim of this project is to discuss the importance of Planar Graphs and
Coloring. In modeling the real-world problems, more complex and advance
structures are needed. Here come the notions of planar graph and the concept of
coloring to make the modeling by graphs more efficient.
However at the beginning of this project report we introduce some basic
concepts and certain properties of graphs to develop the foundation in understanding
the subsequent chapters.
In this project, besides providing an exposure to the definition of planar
graphs, and relevant examples, identification of planarity and nonplanarity are
described with simple examples. Then Euler's formula and Kuratowski's theorem
are used in showing the nonplanarity of K5 and K3,3.
Nevert~eless, a special kind of graphs called, 'trees' are also planar graphs.
So the notions relating to trees, properties and characterizations of trees are
discussed. Trees are known to have wide applications in operation research,
networking and so on. We describe the problem of minimum spanning tree model to
end this chapter.
In graph coloring we have addressed the history behind the four - color
problem. Then, we have included theorems on vertex coloring in planar graphs and
in the end of this discussion, applications of graph coloring in solving common
problems such as examination scheduling to avoid conflicts and storage of chemicals
to prevent adverse interactions are described.
Finally the project ends with a simple summary of findings and suggestion
for future work.
Description
Keywords
GRAPHS , COLORING