Graph theory is a branch of Mathematics that deals with
graphs which are the set of vertices and associated set of edges. Here
we introduce Graph Coloring which is an interesting topic in Graph
theory.
In graph theory, graph coloring is a special case of graph
labeling; it is an assignment...
ABSTRACT
Graph coloring is one of the most important concepts in graph
theory and it has huge number of application in daily life. Graph
coloring is still a very active field of research. The proper coloring of
a graph G is the coloring of the vertices and edges with minimum
numbers of colors. Such that no two vertices should have the same
color .The minimum number of color is called the Chromatic number
(G) and the graph G is called Properly Colored Graph. The
chromatic polynomial is a graph polynomial studied in algebraic
graph theory. It counts the number of graph colorings as a function
of the number of colors. This paper also presents the application of
graph coloring and its importance in various fields.
, CONTENTS
CHAPTER TITLE PAGE NO
INTRODUCTION 1
1 PRELIMINARIES 3
2 GRAPH COLORING 10
3 CHROMATIC NUMBER,
CHROMATIC POLYNOMIAL, 23
GREEDY ALGORITHM
4 APPLICATION OF GRAPH 34
COLORING
CONCLUSION 39
BIBILIOGRAPHY 40
, INTRODUCTION
Graph theory is a branch of Mathematics that deals with
graphs which are the set of vertices and associated set of edges. Here
we introduce Graph Coloring which is an interesting topic in Graph
theory.
In graph theory, graph coloring is a special case of graph
labeling; it is an assignment of labels traditionally called “colors” to
elements of a graph subject to certain constrains. In its simplest
form, it is a way of coloring the vertices of a graph such that no two
adjacent vertices are of the same color; this is called a vertex
Coloring. Similarly, an edge coloring assigns a color to each edge so
that no two adjacent edges are of the same color.
The Chromatic number of a graph is the smallest number of
colors with which the graph can be properly colored. The Chromatic
Polynomial is a graph polynomial studied in algebraic graph theory.
It counts the number of graph colorings as a function of the number
of colors and was originally defined by George Wavid Birkhoff to
study the four color problem. Greedy Algorithm is used for finding
chromatic number of any given graph.
Graph coloring enjoys many practical applications as well as
theoretical challenges. Beside the classical types of problems,
1
, different limitations can also be set on the graph, or on the way a
color is assigned, or even on the color itself. It has even reached
popularity with the general public in the form of the popular number
puzzle Sudoku. Graph coloring is still a very active field of research.
The Graph coloring problem has numerous applications in
Making Schedule or Time table, Sudoku, Aircraft Scheduling, GSM
Mobile phone Network and more.
This Project consist of four chapter. In the first chapter we will
discuss some basic definition example that describes the preliminary
concepts that lays down a basis for the theory of Graph coloring.
In the second chapter deals with Graph coloring, Vertex
coloring, Edge coloring and also contains definition, theorem and
there sub related example. Third chapter explains Chromatic
number, Chromatic Polynomial, Greedy Algorithm and also contains
definition, theorem and problems.
Finally we moves to the last chapter of this project which
concern with the application of Graph coloring in various field of
science.
2
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller anilendhuav. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.59. You're not tied to anything after your purchase.
