3.1.1. Vertex Colouring Motivation

The problem is that of exam time table scheduling. So, there are n subjects in a college. Imagine there is a college with n subjects; multiple students taking those subjects and we need to schedule the exams for those n subjects and we need to schedule the exams in such a way that it should not happen that a student has 2 exams in the same time slot appearing in the schedule.

In an educational institution, the challenge lies in creating an exam timetable. When there are multiple subjects, we have to ensure that no student is scheduled to take two exams at the same time. Each exam corresponds to a different subject, and consequently, if a student is enrolled in multiple classes, the scheduling must avoid conflicts in timing for those subjects.

Consider a student who is enrolled in Math and Science. If the exams for both subjects are scheduled on the same day at the same hour, the student will face a conflict. To illustrate, if Math is at 10 AM and Science is also at 10 AM, that student won't be able to attend both. Therefore, proper scheduling is essential to ensure each student can attend all their exams.

So, how do we model this problem as a graph theoretic problem? So, the n subjects will form the n nodes of my graph. And what will be the edge set so I will add an edge between node number i and node number j which you can interpret as subject number i and subject number j. So, subject number i and subject number j will have an edge among them if there is at least one student who has registered both for the subject i as well as the subject j.

To solve the scheduling issue efficiently, we can represent the subjects and their relationships using a graph. Each subject is a node (vertex) in the graph. An edge between two nodes signifies that a student is enrolled in both subjects, indicating a conflict. If there’s no edge, then the exams for those subjects can occur simultaneously without any student conflicts.

Imagine a social network where each person is a subject. If two people know each other, there’s a connection (edge). In our exam situation, if two subjects have a connection through a student who takes both subjects, then those subjects can’t be examined at the same time. A graph helps visualize and structure these relationships.

I will be interested to colour the nodes of the graph by various colours. And my colouring should satisfy the condition that no two adjacent nodes should get the same colour. And the number of time slots or minimum number of time slots I require is the same as the minimum number of colours needed to colour the vertices.

In graph theory, colouring a graph means assigning colours to vertices under the constraint that adjacent vertices do not share the same colour. For the exam scheduling problem, each unique colour represents a separate time slot. Thus, the goal is to minimize the number of colours used while ensuring no connected subjects (nodes with an edge) are assigned the same colour.

Think of it as organizing different colored post-it notes on your desk. If you have multiple colors and need to ensure no two notes that are near each other (subject to the same student) share the same color, the task becomes about strategically arranging them to reduce the total number of colors used.

Of course, a trivial way to colour the vertices will you take n distinct colours and assign one distinct colour to each of the n vertices. I do not want to do that but because that is equivalent to saying that I conduct exams for the n subjects taking n slots.

The simplest but most inefficient way to solve the colouring problem would be to give each subject its own unique time slot, i.e., color each vertex with a distinct colour. However, this is not practical or resource-efficient, as it would require a time slot for every subject, leading to potential over-scheduling and wastage of resources.

If you think of a restaurant managing its tables, assigning every single customer a separate table would lead to overcrowding and inefficiency. Instead, they could combine smaller groups, serving more customers simultaneously, which is analogous to using fewer time slots efficiently.

This algorithm is based on the greedy strategy which is a very popular strategy in algorithm designs. So, what exactly is the greedy strategy here: the greedy strategy is that you use the first available colour at every step if possible, if not possible then use a new colour.

The greedy colouring algorithm works by selecting each uncoloured vertex and colouring it with the lowest available colour that does not conflict with the already coloured adjacent vertices. This iterative approach ensures that we attempt to minimize the number of colours used while adhering to the rules of colouring.

Imagine you’re painting a room with different sections. You look at each wall (vertex) and select the first available colour (the lowest numbered colour) not already used by the adjacent wall (neighbors). If the colors are all taken, you’ll decide to use a new shade instead.

--