PLANAR GRAPHS AND COLORING
| dc.contributor.author | MANOGARAN, LAVANEESVARI | |
| dc.date.accessioned | 2016-01-28T07:23:58Z | |
| dc.date.available | 2016-01-28T07:23:58Z | |
| dc.date.issued | 2010-05 | |
| dc.description.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. | en_US |
| dc.identifier.uri | http://hdl.handle.net/123456789/1725 | |
| dc.subject | GRAPHS | en_US |
| dc.subject | COLORING | en_US |
| dc.title | PLANAR GRAPHS AND COLORING | en_US |
| dc.type | Thesis | en_US |
Files
License bundle
1 - 1 of 1
Loading...
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: