GRAPH COLORING AND APPLICATIONS

Graph theory , one of the most important topic of computer science carries a great significance in algorithms and data structure. It is indispensable part for any problem solvers in programming. Among so many parts of graph theory , one interesting and easy to understand subtopic that could solve a lot of problems in real world is graph coloring and we are going to discuss and apply it here.

Let’s start from basics.

DEFINITION

Graph coloring is simply assignment of colors to each vertex of a graph so that no two adjacent vertices are assigned the same color.

If you wonder what adjacent vertices are look at the below diagram.

The vertices are c1,c2,c3 and c4. And one pair of adjacent vertices are c1 and c3. Can you guess others?

They are (c1,c4) and (c3,c2). Why ? Because they are connected by edges. You can see them getting connected by edges clearly on the above graph.

And the definition of graph coloring is depicted by above graph which says no two adjacent vertices are assigned the same color and none are in the above graph.

Now after we have basic understanding of what graph coloring is ,let’s move onto its applications.

APPLICATIONS

There are many applications of graph coloring which are really interesting to study about .Let’s list few of them:

1. Exam scheduling

2. Frequency assignment in radio stations

3.Finding out no of index registers to store variables temporarily during execution of loop

But here , we will be dealing with exam scheduling which is the most interesting one to know about and easy to grasp as well.

EXAM SCHEDULING

Let’s suppose algebra, physics, statistics and calculus are four courses of study in our college. And let’s say that following pairs have common students :

1. algebra and statistics
2. algebra and calculus
3. statistics and physics

Problem: Say algebra and statistics exam is held on same day then students taking both courses have to miss at least one exam. They can’t take both at same time. How do we schedule exams in minimum no of days so that courses having common students are not held on same day?

Solution: Graph coloring.

First draw a graph with courses as vertex and they are connected by edges if they have common students. Second color the graph such that no two adjacent vertices are assigned the same color as shown below:

Look at the above graph. It solves our problem. We can conduct exam of courses on same day if they have same color.

Our solution:
DAY 1: Algebra and Physics
DAY 2: Statistics and Calculus

This solves our problem of scheduling exams so that all students can take exams without worrying about missing one.

CHROMATIC NUMBER:

Academically , the least no of colors required to color the graph G is called Chromatic number of the graph denoted by χ(G). χ is read as chi.
And for above example χ(G)=2 because 2 is minimum number of colors required to color above graph.

This is all about graph coloring fundamentals which we need to understand to solve a wide variety of problems in real world. You could research more on it.

And yeah you might be wondering whether there any specific algorithms to solve this problem .There are but there have been no efficient algorithm known that we could use to solve graph coloring problems.

You might be the one to do it. Good luck. Keep learning. Keep inspiring .

Thank you .😀