Graph coloring

Graph coloring

1. PUNDRA UNIVERSITY OF
SCIENCE & TECHNOLOGY
PRESENTATION ON:
GRAPH COLORING
1
Name: Delowar Hossain
Dolon
ID: 00817206031
Batch: 2
nd

Semester: 6
th

Department of CSE
Name: Abu Rayhan
Designation: Lecturer in
CSE
Department of CSE
Submitted By Submitted To

2. WHAT IS GRAPH COLORING?
Graph coloring is an assignment of colors
(or any distinct marks) to the vertices of a
graph. Strictly speaking, a coloring is a
proper coloring if no two adjacent vertices
have the same color.


There are two types of graph coloring :
 Edge coloring
 Vertex coloring
2

3. WHY GRAPH COLORING?
 Many problems can be formulated as a graph
coloring problem including time tabling, channel
assignment etc.
A lot of research has been done in this area.
Find a channel assignment to radio stations such
that no station has a conflict (there is a conflict if
they are in vicinity)
Vertices – radio stations, edges – conflict, colors –
available channels
3

4. GRAPH COLORING ALGORITHM
There is no efficient algorithm available for
coloring a graph with minimum number of colors.
Graph coloring problem is a known np complete
problem.
Np complete problems are problems whose status
is unknown.
No polynomial time algorithm has yet been
discovered for any np complete problem.
It is not established that no polynomial time
algorithm exist for any of them.
4

5. NP COMPLETE PROBLEM
The interesting part is, if any one of the NP
complete problems can be solved in polynomial
time, then all of them can be solved.
 Although graph coloring problem is np complete
problem there are some approximate algorithms
to solve the graph coloring problem.
5

6.  GREEDY ALGORITHM
Color first vertex with first color.
Do following for remaining v-1 vertices. A)
consider the currently picked vertex and color it
with the lowest numbered color that has not been
used on any previously colored vertices adjacent
to it. If all previously used colors appear on
vertices adjacent to v, assign a new color to it.
6

7. WELSH POWELL ALGORITHM 
 Find the degree of each vertex.
 List the vertices in order of descending valence
i.e. Degree(v(i))>=degree(v(i+1))
 Color the first vertex in the list
 Go down the sorted list and color every vertex
not connected to the colored vertices above the
same color then cross out all colored vertices in
the list.
 Repeat the process on the uncolored vertices
with a new color always working in descending
order of degree until all vertices are colored.
7

8. APPLICATIONS OF GRAPH
COLORING
SUDOKU
 SCHEDULING
 MOBILE RADIO FREQUENCY ASSIGNMENT
PATTERN MATCHING
 REGISTER ALLOCATION
 TIME TABLING
CHANNEL ASSIGNMENT, ETC.
8

9. CONCLUSION
 Graph coloring is a np-complete problem.
Using greedy approach, always doesn’t gives
minimum required number of color.
Using above algorithm, the color depends on the
processing of vertices.
 Also if any algorithm can solve this problem,
then all np complete problems can be solved.
9

10. .
10