Scribd
Upload
19 views6 pages

Graph Coloring Algorithm Explained

Graph coloring is the process of assigning colors to vertices of a graph such that no two adjacent vertices share the same color, with the goal of minimizing the number of colors used, known as the chromatic number. The document outlines a method for coloring a graph using a systematic approach and discusses various applications of graph coloring, including register allocation and map coloring. Additionally, it mentions the use of backtracking to assign colors while ensuring no adjacent vertices have the same color.

Uploaded by

sima.171003
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views6 pages

Graph Coloring Algorithm Explained

Graph coloring is the process of assigning colors to vertices of a graph such that no two adjacent vertices share the same color, with the goal of minimizing the number of colors used, known as the chromatic number. The document outlines a method for coloring a graph using a systematic approach and discusses various applications of graph coloring, including register allocation and map coloring. Additionally, it mentions the use of backtracking to assign colors while ensuring no adjacent vertices have the same color.

Uploaded by

sima.171003
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

GRAPH COLORING ALGORITHM

Graph coloring is the procedure of assignment of colors to each vertex of a graph G such that no adjacent vertices
get same color. The objective is to minimize the number of colors while coloring a graph. The smallest number of
colors required to color a graph G is called its chromatic number of that graph. Graph coloring problem is a NP
Complete problem.

Method to Color a Graph


The steps required to color a graph G with n number of vertices are as follows −

Step 1 − Arrange the vertices of the graph in some order.

Step 2 − Choose the first vertex that has highest degree and color it with the first color.

Step 3 − Choose the next vertex and color it with the lowest numbered color that has not been colored on any
vertices adjacent to it. If all the adjacent vertices are colored with this color, assign a new color to it. Repeat this step
until all the vertices are colored.

Example

In the above figure, at first vertex a is colored red. As the adjacent vertices of vertex a are
again adjacent, vertex b and vertex d are colored with different color, green and blue
respectively. Then vertex c is colored as red as no adjacent vertex of c is colored red. Hence,
we could color the graph by 3 colors. Hence, the chromatic number of the graph is 3.
Applications of Graph Coloring
Some applications of graph coloring include −

Register Allocation
Map Coloring
 Bipartite Graph Checking
 Mobile Radio Frequency Assignment
 Making time table, etc.
 Vertex coloring is the most commonly encountered graph coloring problem. The
problem states that given m colors, determine a way of coloring the vertices of a graph
such that no two adjacent vertices are assigned same color.

 Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are
of the same color, and a face coloring of a planar graph assigns a color to each face or
region so that no two faces that share a boundary have the same color.

 The smallest number of colors needed to color a graph G is called its chromatic number.
Since each node can be colored by using any of the m colors, the total numbers of
possible color configurations are mv. The complexity is exponential which is very
huge.

Using Backtracking:
 By using the backtracking method, the main idea is to assign colors one by one to
different vertices right from the first vertex (vertex 0).
 Before color assignment, check if the adjacent vertices have same or different color
by considering already assigned colors to the adjacent vertices.
o If the color assignment does not violate any constraints, then we mark that
color as part of the result. If color assignment is not possible then backtrack
and return false.
Chromatic number:
The following table gives the chromatic numbers for some named classes of graphs.

graph

complete graph

cycle graph ,

star graph , 2

wheel graph ,
In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a
single universal vertex to all vertices of a cycle.

MAP coloring:

You might also like