Graph colouring

It is related to Graph Theory. Graph colouring is important for Computer science & Engineering.

1. Maulana Azad National Maulana Azad National InstituteInstitute of of
TechnologyTechnology
Department of Computer Science & EngineeringDepartment of Computer Science & Engineering
Presentation Presentation
OnOn
Graph ColoringGraph Coloring
Presented By:Presented By:
Priyank JainPriyank Jain
Shweta SaxenaShweta Saxena

2. What is Graph Coloring?What is Graph Coloring?
Graph Coloring is an assignment of colors Graph Coloring is an assignment of colors
(or any distinct marks) to the vertices of a (or any distinct marks) to the vertices of a
graph. Strictly speaking, a coloring is a graph. Strictly speaking, a coloring is a
proper coloring if no two adjacent vertices proper coloring if no two adjacent vertices
have the same color.have the same color.

3. Origin of the problemOrigin of the problem

4. Origin of the problemOrigin of the problem

5. Why Graph Coloring?Why Graph Coloring?
Many problems can be formulated as a Many problems can be formulated as a
graph coloring problem including Time graph coloring problem including Time
Tabling, Tabling, Channel AssignmentChannel Assignment etc. etc.
A lot of research has been done in this A lot of research has been done in this
area.area.

6. Channel AssignmentChannel Assignment
Find a channel assignment to R radio Find a channel assignment to R radio
stations such that no station has a conflict stations such that no station has a conflict
(there is a conflict if they are in vicinity)(there is a conflict if they are in vicinity)
Vertices – radio stations, edges – conflict, Vertices – radio stations, edges – conflict,
colors – available channelscolors – available channels

7. TerminologyTerminology
K-ColoringK-Coloring
A k-coloring of a graph G is a mapping of A k-coloring of a graph G is a mapping of
V(G) onto the integers 1..k such that adjacent V(G) onto the integers 1..k such that adjacent
vertices map into different integers.vertices map into different integers.
A k-coloring partitions V(G) into k disjoint A k-coloring partitions V(G) into k disjoint
subsets such that vertices from different subsets such that vertices from different
subsets have different colors.subsets have different colors.

8. TerminologyTerminology
K-colorableK-colorable
A graph G is k-colorable if it has a k-coloring.A graph G is k-colorable if it has a k-coloring.
Chromatic NumberChromatic Number
The smallest integer k for which G is k-The smallest integer k for which G is k-
colorable is called the chromatic number of G.colorable is called the chromatic number of G.

9. TerminologyTerminology
K-chromatic graphK-chromatic graph
A graph whose chromatic number is k is A graph whose chromatic number is k is
called a k-chromatic graph.called a k-chromatic graph.
ColoringColoring
A coloring of a graph G assigns colors to the A coloring of a graph G assigns colors to the
vertices of G so that adjacent vertices are vertices of G so that adjacent vertices are
given different colorsgiven different colors

10. ExampleExample
The chromatic number is four. Therefore this a 4-Chromatic Graph

11. ExampleExample
Problem: A state legislature has a Problem: A state legislature has a
number of committees that meet each number of committees that meet each
week for one hour. How can we schedule week for one hour. How can we schedule
the committee meetings times such that the committee meetings times such that
the least amount of time is used but such the least amount of time is used but such
that two committees with overlapping that two committees with overlapping
membership do not meet at the same membership do not meet at the same
time.time.

12. Example (cont)Example (cont)
The chromatic number of this graph is four. Thus four hours suffice to schedule
committee meetings without conflict.
An edge represents a conflict between to meetings
An vertex represents a meeting

13. Graph Colouring AlgorithmGraph Colouring Algorithm
There is no efficient algorithm available for There is no efficient algorithm available for
coloring a graph with minimum number of coloring a graph with minimum number of
colors.colors.
 Graph coloring problem is a known NP Graph coloring problem is a known NP
Complete problem. Complete problem.

14. NP Complete Problem NP Complete Problem
NP complete problems are problems NP complete problems are problems
whose status is unknown. whose status is unknown.
No polynomial time algorithm has yet No polynomial time algorithm has yet
been discovered for any NP complete been discovered for any NP complete
problemproblem
 It is not established that no polynomial-It is not established that no polynomial-
time algorithm exist for any of them. time algorithm exist for any of them.

15. NP Complete ProblemNP Complete Problem
The interesting part is, if any one of the The interesting part is, if any one of the
NP complete problems can be solved in NP complete problems can be solved in
polynomial time, then all of them can be polynomial time, then all of them can be
solved.solved.
Although Graph coloring problem is NP Although Graph coloring problem is NP
Complete problem there are some Complete problem there are some
approximate algorithms to solve the graph approximate algorithms to solve the graph
coloring problem.coloring problem.

16. Basic Greedy AlgorithmBasic Greedy Algorithm
1.1.Color first vertex with first color.Color first vertex with first color.
2. Do following for remaining V-1 vertices. 2. Do following for remaining V-1 vertices.
a) a) Consider the currently picked vertex Consider the currently picked vertex
and color it with the lowest numbered and color it with the lowest numbered
color that has not been used on any color that has not been used on any
previously colored vertices adjacent to it. previously colored vertices adjacent to it.
If all previously used colors appear on If all previously used colors appear on
vertices adjacent to v, assign a new color vertices adjacent to v, assign a new color
to it. to it.

17. Analysis of Greedy AlgorithmAnalysis of Greedy Algorithm
The above algorithm doesn’t always use The above algorithm doesn’t always use
minimum number of colors. Also, the minimum number of colors. Also, the
number of colors used sometime depend number of colors used sometime depend
on the order in which vertices are on the order in which vertices are
processedprocessed

18. Example:Example:
For example, consider the following two For example, consider the following two
graphs. Note that in graph on right side, graphs. Note that in graph on right side,
vertices 3 and 4 are swapped. If we vertices 3 and 4 are swapped. If we
consider the vertices 0, 1, 2, 3, 4 in left consider the vertices 0, 1, 2, 3, 4 in left
graph, we can color the graph using 3 graph, we can color the graph using 3
colors. But if we consider the vertices 0, 1, colors. But if we consider the vertices 0, 1,
2, 3, 4 in right graph, we need 4 colors2, 3, 4 in right graph, we need 4 colors

19. Analysis of Basic AlgorithmAnalysis of Basic Algorithm

20. WelshWelsh Powell Powell AlgorithmAlgorithm
Find the degree of each vertexFind the degree of each vertex
ListList the verices the verices in order of descending in order of descending
valence i.e. valence i.e. degree(v(i))>=degree(v(i+1))degree(v(i))>=degree(v(i+1))
Colour Colour the first vertex in the listthe first vertex in the list
Go down the sorted list and color every Go down the sorted list and color every
vertex not connected to the colored vertex not connected to the colored
vertices above the same color then cross vertices above the same color then cross
out all colored vertices in the list.out all colored vertices in the list.

21. Welsh Powell AlgorithmWelsh Powell Algorithm
Repeat the process on the uncolored Repeat the process on the uncolored
vertices with a new color-always working vertices with a new color-always working
in descending order of degree until all in descending order of degree until all
vertices are colored.vertices are colored.
Complexity Complexity of above algorithm = of above algorithm = O(nO(n
22
))

22. Welsh Powell Algorithm: Welsh Powell Algorithm:
ExampleExample

23. Welsh Powell Algorithm: Welsh Powell Algorithm:
Example Example

24. Welsh Powell Algorithm: Welsh Powell Algorithm:
Example Example

25. Welsh Powell Algorithm: Welsh Powell Algorithm:
Example Example

26. Welsh Powell Algorithm: Welsh Powell Algorithm:
Example Example

27. Welsh Powell Algorithm: Welsh Powell Algorithm:
Example Example

28. Any QueriesAny Queries

29. Thank YouThank You