Graph
Coloring Problem
Course code: 0613-205
Course Title: Algorithms
Batch: D-90, Group: F
Name: Roll:
Tasfir Ahammed Tanvir 19 Mazharul Hasan
Talha Ibn Musa 25 Lecturer
Subrata Halder 30 Dept. Of CSE
Arfatul Aziz Maruf 33 Dhaka International University
Tanimul Haque Tanim 40
Partha Halder 44
Contents
❑ Introduction
❑ Types of Graph Coloring
❑ Graph Coloring approach
❑ Algorithms
❑ Example
❑ Applications
❑ Complexity Analysis
❑ Conclusion
❑ Q&A
2
Introduction
Graph coloring is the process of coloring the vertices of a graph so that no two
connected (adjacent) vertices have the same color.
3
Types of graph coloring
Vertex Coloring: Coloring vertices so that no two adjacent vertices share the same color.
Edge Coloring: Coloring edges so that no two edges sharing the same vertex have the same
color.
Map coloring: Coloring regions (faces) of a planar graph so that no two adjacent regions
share the same color.
4
The Chromatic Number
The smallest number of colors needed to color a graph G is called its
chromatic number.
For example, the following can be colored minimum 3 colors.
m=3 (R,G,B)
A B
C D
5
Graph coloring approach
Backtracking: Tries all color combinations recursively and backtracks on conflicts.
How It Works:
➢ Start from the first vertex.
➢ Try assigning one of the m colors.
➢ Check if the color is valid (not the same as any adjacent vertex).
➢ If valid, move to the next vertex.
➢ If stuck (no valid color), go back to the previous vertex and try a different color.
➢ Repeat until all vertices are colored or no solution is possible.
6
Graph coloring Backtracking
Example Problem: n=4, m=3
n A B C D
A B A 0 1 0 1
B 1 0 1 0
C 0 1 0 1
D C
D 1 0 1 0
Undirected graph
Adjacency matrix
7
Algorithms
8
If available color m=3
State Space Tree RED, GREEN, BLUE
1 2
V=4
4 3
V1
V2
V3
V4
……………………………………………………
9
If available color m=3
Graph coloring using Backtracking RED, GREEN, BLUE
1 2
V=4
4 3
V1
V2
V3
V4
10
Graph coloring Backtracking
1 2
4 3
i. R, G, R, G
ii. R, G, R, B
iii. R, G, B, G
iv. R, B, R, G
v. R, B, R, B
11
Complexity Analysis
In this method each vertex has m different choices of colors. So the total
time complexity is 𝑚𝑛 , where m is the number of colours and n is the
number of vertices.
O(𝑚𝑛 )
Where,
n= number of vertices
m=number of colors
12
Graph coloring has practical applications
1. Making Schedule or time table
2. Sudoku
3. Frequency Assignment
4. Register allocation
5. Bipartite graph
6. Map Coloring
13
Conclusion
The graph coloring problem assigns colors to vertices so no two
adjacent ones share the same color, aiming to minimize the number of
colors used.
It is NP-hard with applications in scheduling, resource allocation, and
network design.
14
Thank You
Q&A
15
