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
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
